Неужели я становлюсь функциональным извращенцем? - Декларативное программирование

Дбрый день, товарищи!
Читаю SICP, где-то четверть уже прочитал. Вчера понял, как спомощью функций можно описывать абстракции (суммирование,перемножение->аккумуляция). Еще чуть-чуть и кажется помойму как проектировать в терминах ФП — это что уже диагноз?

Здравствуйте, mini_root_2, Вы писали:

__>Дбрый день, товарищи!
__>Читаю SICP, где-то четверть уже прочитал. Вчера понял, как спомощью функций можно описывать абстракции (суммирование,перемножение->аккумуляция). Еще чуть-чуть и кажется помойму как проектировать в терминах ФП — это что уже диагноз?

Оставайтесь на месте. За вами скоро приедут.

...Санитары

... << RSDN@Home 1.2.0 alpha rev. 648>>

Здравствуйте, mini_root_2, Вы писали:

__>Дбрый день, товарищи!
__>Читаю SICP, где-то четверть уже прочитал. Вчера понял, как спомощью функций можно описывать абстракции (суммирование,перемножение->аккумуляция). Еще чуть-чуть и кажется помойму как проектировать в терминах ФП — это что уже диагноз?

Здорово! Ещё один выздоравливает.

Здравствуйте, mini_root_2, Вы писали:

__>Дбрый день, товарищи!
__>Читаю SICP, где-то четверть уже прочитал. Вчера понял, как спомощью функций можно описывать абстракции (суммирование,перемножение->аккумуляция). Еще чуть-чуть и кажется помойму как проектировать в терминах ФП — это что уже диагноз?

в качестве меры профилактики рекомендуется ежедневно заниматься оптимизацией программ

Здравствуйте, BulatZiganshin, Вы писали:

BZ>Здравствуйте, mini_root_2, Вы писали:

__>>Дбрый день, товарищи!
__>>Читаю SICP, где-то четверть уже прочитал. Вчера понял, как спомощью функций можно описывать абстракции (суммирование,перемножение->аккумуляция). Еще чуть-чуть и кажется помойму как проектировать в терминах ФП — это что уже диагноз?

BZ>в качестве меры профилактики рекомендуется ежедневно заниматься оптимизацией программ

И чем мне это поможет? Лучше уж писать на vba по два часа в день до полного разжижения мозга..

.

Здравствуйте, mini_root_2, Вы писали:

__>Дбрый день, товарищи!
__>Читаю SICP, где-то четверть уже прочитал. Вчера понял, как спомощью функций можно описывать абстракции (суммирование,перемножение->аккумуляция). Еще чуть-чуть и кажется помойму как проектировать в терминах ФП — это что уже диагноз?

Описывать абстракции это одно. А вот прочитывать абстракции это другое.

Вот пытался давеча такую абстракцию прочитать:

(define-syntax cond
  (lambda (x)
    (syntax-case x ()
      ((_ c1 c2 ...)
       (let f ((c1 (syntax c1)) (cmore (syntax (c2 ...))))
         (if (null? cmore)
             (syntax-case c1 (else =>)
               ((else e1 e2 ...) (syntax (begin e1 e2 ...)))
               ((e0) (syntax (let ((t e0)) (if t t))))
               ((e0 => e1) (syntax (let ((t e0)) (if t (e1 t)))))
               ((e0 e1 e2 ...) (syntax (if e0 (begin e1 e2 ...)))))
             (with-syntax ((rest (f (car cmore) (cdr cmore))))
               (syntax-case c1 (=>)
                 ((e0) (syntax (let ((t e0)) (if t t rest))))
                 ((e0 => e1) (syntax (let ((t e0)) (if t (e1 t) rest))))
                 ((e0 e1 e2 ...)
                  (syntax (if e0 (begin e1 e2 ...) rest)))))))))))

Тут одним стаканом не обойдешься. Это ж сколько стаканов нужно употребить, чтобы такое сходу прочитывать?

Здравствуйте, mini_root_2, Вы писали:

__>Дбрый день, товарищи!
__>Читаю SICP, где-то четверть уже прочитал. Вчера понял, как спомощью функций можно описывать абстракции (суммирование,перемножение->аккумуляция). Еще чуть-чуть и кажется помойму как проектировать в терминах ФП — это что уже диагноз?

Не, рано пока ставить диагноз... Ты ещё Haskell с его монадами не видел

Я тоже, когда прочитал sicp, думал, что всё теперь в ФП понимаю

.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, frogkiller, Вы писали:

F>Не, рано пока ставить диагноз... Ты ещё Haskell с его монадами не видел

Монады — фигня!
Достаточно вкурить в 4 разных монады — Maybe, State, List, IO — чтобы все остальные монады на одной затяжке проходили.
Maybe — самый простой контейнер (не считая Id, естественно), просто обёртка данных
State — "не просто" обёртка данных, а ещё и изменчивая среда с функциями, определёнными над ней
List — хранилище множества данных, демонстрирующее монадную арифметику во всей красе.
IO — частный случай State, чертовски защищённый от расковыривания. Что в IO попало, то пропало.

Вот когда стрелки будут не фигнёй, вот тогда точно уже диагноз.

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, last shinji, Вы писали.

Кстати, вот.

Два разных определения do

(define-syntax do
  (lambda (x)
    (syntax-case x ()
      ((_ (binding ...) (test res ...) exp ...)
       (with-syntax ((((var val update) ...)
                      (map (lambda (b)
                             (syntax-case b ()
                               ((var val)
                                (syntax (var val var)))
                               ((var val update)
                                (syntax (var val update)))))
                           (syntax (binding ...)))))
         (syntax (let doloop ((var val) ...)
                   (if test
                       (begin (if #f #f) res ...)
                       (begin exp ... (doloop update ...))))))))))

(define-syntax do
  (lambda (orig-x)
    (syntax-case orig-x ()
      (( ((var init . step) ... ) (e0 e1 ... ) c ... )
       (with-syntax (((step ... )
                      (map (lambda (v s)
                             (syntax-case s ()
                               (() v)
                               ((e) (syntax e))
                               ( (syntax-error orig-x))))
                           (syntax (var ... ))
                           (syntax (step ... )))))
         (syntax-case (syntax (e1 ... )) ()
           (() (syntax (let doloop ((var init) ... )
                         (if (not e0)
                             (begin c ... (doloop step ... ))))))
           ((e1 e2 ... )
            (syntax (let doloop ((var init) ... )
                      (if e0
                          (begin e1 e2 ... )
                          (begin c ... (doloop step ... ))))))))))))

Помогите, пожалуйста, понять как используюстя паттерны ((var val update) ...) и (step ... ), к ним привязывается что-то или они предварительно раскрываются?

Здравствуйте, last shinji, Вы писали:
...
Макрос — это маленький компилятор, зачастую он довольно сложно преобразует передданое в него AST.

LS>Помогите, пожалуйста, понять как используюстя паттерны ((var val update) ...) и (step ... ), к ним привязывается что-то или они предварительно раскрываются?

Намек есть вот тут: http://www.rsdn.ru/Forum/message/2233442.1.aspx
А вообще нужно читать Дибвига (он, кстати, автор переносимой реализации syntax-case): http://www.scheme.com/tspl3/

BZ>>в качестве меры профилактики рекомендуется ежедневно заниматься оптимизацией программ

__>И чем мне это поможет? Лучше уж писать на vba по два часа в день до полного разжижения мозга..

.

я на днях даже от gcc плевался. представьте, себе, такой вот код:

byte *p;
x = *p/16;

он превращает в

movzl (%ebx), eax
shrb  al, 4
movzl al, eax

прям хоть ассемблерные вставки делай

а вы тут — хаскел, фп, монады. эх, где мои семнадцать лет, когда у меня в программе даже sp был задействован для хранения своих данных

Здравствуйте, frogkiller, Вы писали:

F>Не, рано пока ставить диагноз... Ты ещё Haskell с его монадами не видел

F>Я тоже, когда прочитал sicp, думал, что всё теперь в ФП понимаю

.

Добрый день, товарищи!

Уря! Оказывается я еще практически здоров! Вчера поставил себе немерле на моно и понял, что до настоящих извращенцев мне еще далеко (не будем показывать пальцем...). Читал статью в переводе Влада, долго думал что означает сие:

[Hygienic]
cache(e : Expr) : Expr * Expr
{ | <[ $obj.$mem ]> => (<[ def tmp = $obj ]>, <[ tmp.$mem ]>) 
  | <[ $tab [$idx] ]> => 
    (<[ def (tmp1, tmp2) = ($tab, $idx) ]>, <[ tmp1 [tmp2] ]>)
  | _ => (<[()]>, e)
}

Т.е понятно что это конструкция match/case, которая меняет местами значения двух переменных, но совершенно непонятно зачем там квази цитирование (да и вообще макросы? я видел в статье упоминание случайных элементов массива, но все равно не совсем понятно)?
P.S. Что-то меня от немерле не торкнуло — видимо надо увеличить дозу

.

Здравствуйте, mini_root_2, Вы писали:

__>P.S. Что-то меня от немерле не торкнуло

Не боишся, что тебя забанят?

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>Не боишся, что тебя забанят?

За то что не торкнуло? Ну это поправимо, вот приду сеогдня домой — сяду писать интерпретатор брейнфака на немерле (главное догадаться куда впихнуть макросы, и вообще для чего они там нужны...).

P.S. А что на РСДН действует тайная секта немерлистов-фундаменталистов, которые банят всех кого не торкнуло после хело ворда (обязательно с использованием самопального макроса println) на немерле?

__>P.S. Что-то меня от немерле не торкнуло — видимо надо увеличить дозу

.

и ждать прихода розового слоника

Здравствуйте, Кодт, Вы писали:

К>Монады — фигня!
К>Достаточно вкурить в 4 разных монады — Maybe, State, List, IO — чтобы все остальные монады на одной затяжке проходили.
К>Maybe — самый простой контейнер (не считая Id, естественно), просто обёртка данных
К>State — "не просто" обёртка данных, а ещё и изменчивая среда с функциями, определёнными над ней
К>List — хранилище множества данных, демонстрирующее монадную арифметику во всей красе.
К>IO — частный случай State, чертовски защищённый от расковыривания. Что в IO попало, то пропало.

Мне как прожжёному императивщику даже эти 4 монады кажутся сильно страшными. Единственный лучик света, что я пока встречал — статья в LinuxJournal.

Там, в частности, рассмотрена упомянутая тобой Maybe. Правда реализованная на не совсем императивных языках, в которых имеются замыкания. Я тут попробовал переписать этот пример на С++, получилось так:

#include <iostream>

template <typename TValue, class TInstance>
struct CMonadDef
{
    struct CMyFunctor
    {
        virtual TInstance apply(const TValue &) = 0;
    };
};

template <typename TValue, class TInstance>
class CMonad
{
protected:
    TValue m_value;    
    CMonad() {}

public:
    CMonad(const TValue &_value) : m_value(_value) {}

    typedef typename CMonadDef<TValue, TInstance>::CMyFunctor CMyFunctor;
    typedef TValue TVal;

    virtual TInstance pass(CMyFunctor * pfn)
    {
        return pfn->apply(m_value);
    }
};

template <typename T, class TInstance>
class CMaybe : public CMonad<T, TInstance>
{
    bool m_bNone;

public:
    struct None {};
    static None & getNone()
    {
        static None none;
        return none;
    }

    typedef CMonad<T, TInstance> IParent;

    CMaybe(const T &_value) : IParent(_value), m_bNone(false) {}
    CMaybe(const None &) : m_bNone(true) {}

    virtual TInstance pass(typename IParent::CMyFunctor * pfn)
    {
        if (m_bNone)
        {
            return TInstance(getNone());
        }
        return IParent::pass(pfn);
    }

    void Print() const
    {
        if (m_bNone)
        {
            std::cout << "Maybe(none)" << std::endl;
        }
        else
        {
            std::cout << "Maybe(" << this->m_value << ")" << std::endl;
        }
    }
};

template <typename T, class TMonad>
struct IArithmetic
{
    class CAddFunctor : public TMonad::CMyFunctor
    {
        const T &m_value;
    public:
        CAddFunctor(const T &_value) : m_value(_value) {}
        virtual TMonad apply(const T &_value)
        {
            return TMonad(m_value + _value);
        }
    };
    template <class CApplication, class TAnotherMonad>
    class CMyBinder : public TAnotherMonad::CMyFunctor
    {
        TAnotherMonad &m_value;
    public:
        CMyBinder(TAnotherMonad &_value) : m_value(_value) {}
        virtual TAnotherMonad apply(const typename TAnotherMonad::TVal &_value)
        {
            CApplication app(_value);
            return m_value.pass(&app);
        }
    };

    template <class TAnotherMonad>
    TMonad Add(TAnotherMonad &rhs)
    {
        CMyBinder<CAddFunctor, TAnotherMonad> app(rhs);
        return static_cast<TMonad*>(this)->pass(&app);
    }

    template <class TAnotherMonad>
    friend TMonad operator+ (TMonad &lhs, TAnotherMonad &rhs)
    {
        return lhs.Add(rhs);
    }
};

template <typename T>
struct CArithmeticMaybe : public CMaybe<T, CArithmeticMaybe<T> >, public IArithmetic<T, CArithmeticMaybe<T> >
{
    typedef CMaybe<T, CArithmeticMaybe<T> > CMaybeParent;
    CArithmeticMaybe(const typename CMaybeParent::None &none) : CMaybeParent(none) {}
    CArithmeticMaybe(const T &_value) : CMaybeParent(_value) {}
};

CArithmeticMaybe<int> n1(5), n2(6), n3(CArithmeticMaybe<int>::getNone());

int main(int argc, char* argv[])
{
    n1.Add(n2).Add(n2).Print();
    n1.Add(n2).Add(n3).Print();

    //(n2 + (CArithmeticMaybe<int>)2).Print();
    //((CArithmeticMaybe<int>)CArithmeticMaybe<int>::getNone() + n2).Print();
    return 0;
}

Собственно, я тоже посупил не совсем честно, используя шаблоны, но без них, боюсь, не обойтись. Вот так императивщик воспринимает монады, правда страшно? Как будет выглядеть IO я и подумать-то боюсь...

Оффтоп, вопросы (их, возможно, следовало бы запостить с Cpp):
1. Как бы это хозяйство (ручной бинд функторов в IArithmetic) переписать с помощью boost::lambda? Я в бусте совсем слаб, и все мои попытки что-то использовать оттуда при написании вышеприведённого кода выглядели каким-то шаманством, которое так ни к чему и не привело.

2. Почему не проходит неявное преобразование в двух закомментированных строчках? Я сначала подумал, что это глюк моего MSVC7.1, но Comeau Online тоже они не понравились, он ругается даже на явный каст.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, frogkiller, Вы писали:

F>Здравствуйте, Кодт, Вы писали:

К>>Монады — фигня!
К>>Достаточно вкурить в 4 разных монады — Maybe, State, List, IO — чтобы все остальные монады на одной затяжке проходили.
К>>Maybe — самый простой контейнер (не считая Id, естественно), просто обёртка данных
К>>State — "не просто" обёртка данных, а ещё и изменчивая среда с функциями, определёнными над ней
К>>List — хранилище множества данных, демонстрирующее монадную арифметику во всей красе.
К>>IO — частный случай State, чертовски защищённый от расковыривания. Что в IO попало, то пропало.

F>Мне как прожжёному императивщику даже эти 4 монады кажутся сильно страшными. Единственный лучик света, что я пока встречал — статья в LinuxJournal.

А можно глупый вопрос? Что такое монады и зачем они вообще нужны?
P.S. Можно смело продолжать читать SICP — до настоящих функциональных извращенцев мне еще далеко

...

Здравствуйте, mini_root_2, Вы писали:

__>P.S. А что на РСДН действует тайная секта немерлистов-фундаменталистов, которые банят всех кого не торкнуло после хело ворда (обязательно с использованием самопального макроса println) на немерле?

И банят не тех, кого не торкнуло, а тех, кто занимается неконструктивной критикой Немерла.

... << RSDN@Home 1.2.0 alpha rev. 749>>

__>А можно глупый вопрос? Что такое монады и зачем они вообще нужны?

насколько я в курсе, по ним написано 666 руководств, и всё равно учёные ещё не разобрались до конца

http://www.haskell.org/haskellwiki/Learning_Haskell ищи Monads

Здравствуйте, Блудов Павел, Вы писали:

БП>Здравствуйте, mini_root_2, Вы писали:

__>>P.S. А что на РСДН действует тайная секта немерлистов-фундаменталистов, которые банят всех кого не торкнуло после хело ворда (обязательно с использованием самопального макроса println) на немерле?

БП>И банят не тех, кого не торкнуло, а тех, кто занимается неконструктивной критикой Немерла.

Ой, надо же, это же в корне все меняет.

Какие эти баньшики оказывается, адекватные и спокойные люди.

Эрланг — говно тормозное. Ну? Кто бежит меня арестоффать? Эй, Мамут? Ты там как, нормально пережил неконструктивную критику?

Здравствуйте, BulatZiganshin, Вы писали:

__>>P.S. Что-то меня от немерле не торкнуло — видимо надо увеличить дозу

.

BZ>и ждать прихода розового слоника

Похоже, так никто шутку и не оценил

Для тех, кто не в курсе, посмотрите на подпись Влада.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, mini_root_2, Вы писали:

__>Т.е понятно что это конструкция match/case, которая меняет местами значения двух переменных
Допустим ты пишешь GetSomeValue().Member <-> GetSomeArray()[CalculateSomeIndex()]

Простой макрос @<->(x,y) { <[ def tmp = $x; $x = $y; $y = tmp; ]> } превратит это в:

def tmp = GetSomeValue().Member;
GetSomeValue().Member = GetSomeArray()[CalculateSomeIndex()]
GetSomeArray()[CalculateSomeIndex()] = tmp;

Тот что в стандартной библиотеке с помощью cache делает так, что все посторонние вычисления производятся один раз.

__>но совершенно непонятно зачем там квази цитирование
Непонятно почему тебе непонятно.

>да и вообще макросы?
Макросы затем, чтобы было удобно и эффективно. Конечно можно и без макросов, но это не так удобно, хотя и гораздо проще. Примерно так:

swap[T](ref a : T, ref b : T) { def tmp = b; b = a; a = tmp;  }
 
swap(ref GetSomeValue().Member, ref GetSomeArray()[CalculateSomeIndex()])

__>Уря! Оказывается я еще практически здоров!
Рано радуешься. Может оказаться, что ты не только не здоров, но еще и болен чем-то более серьезным, и уже давно.

__>Вчера поставил себе немерле на моно и понял, что до настоящих извращенцев мне еще далеко (не будем показывать пальцем...).
Кто из нас извращенец еще большой вопрос.

Здравствуйте, mini_root_2, Вы писали:

__>А можно глупый вопрос? Что такое монады и зачем они вообще нужны?

Если коротко и общо, то всё просто.
Было обнаружено, что много разнообразных вещей (а именно, комбинирование элементарных действий) укладывается в примерно одну схему.
Эта схема — обобщение теории групп.
Ну хорошо, в две схемы: монады и стрелки.

После чего отделили однообразные комбинаторы от содержательных вещей, что позволило
— сделать удобный сахар для комбинирования (do-нотацию и list comprehension)
— в ряде случаев абстрагироваться от класса контейнера
— сделать более стройную логику, что позволяет избежать изобретения велосипедов.

Вообще, такая идея — отделять комбинаторы от содержания — очень полезна.
Например, рекурсивная обработка списков: можно на каждый раз писать рукодельный обход, а можно использовать 4 унифицированных обхода — foldr, foldl, foldl', foldM.
Для любителей теории нужно вспомнить про ххххх-морфизмы и прочесть труд "Линзы, бананы и разлохмаченные провода".
После чего уже не возникает желания рожать алгоритмы, связанные с обходом других структур — например, деревьев. Вместо этого, в библиотеку, описывающую тип дерева, добавляются соответствующие функции для построения ана- и катаморфизмов. А дальше пользователь с их помощью выразит всё, что душе угодно.

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Кодт, Вы писали:

К>Для любителей теории нужно вспомнить про ххххх-морфизмы и прочесть труд "Линзы, бананы и разлохмаченные провода".
А можно пару примеров ххххх-морфизмов из жизни? Труд ниасилил.

now playing: Mutt — You'll See

Здравствуйте, Vermicious Knid, Вы писали:

__>>но совершенно непонятно зачем там квази цитирование
VK>Непонятно почему тебе непонятно.

__>>Уря! Оказывается я еще практически здоров!
VK>Рано радуешься. Может оказаться, что ты не только не здоров, но еще и болен чем-то более серьезным, и уже давно.

__>>Вчера поставил себе немерле на моно и понял, что до настоящих извращенцев мне еще далеко (не будем показывать пальцем...).
VK>Кто из нас извращенец еще большой вопрос.

Ты можешь обойтись без перехода на личности? Это очень сложно для тебя, или ты все-таки справишься?

Здравствуйте, EvilChild, Вы писали:

К>>Для любителей теории нужно вспомнить про ххххх-морфизмы и прочесть труд "Линзы, бананы и разлохмаченные провода".
EC>А можно пару примеров ххххх-морфизмов из жизни? Труд ниасилил.
foldr — катаморфизм для списков (др. словами, катаморфизм обходит рекурсивный контейнер и комбинирует значения с помощью переданной функции).
unfoldr — анаморфизм для списков (др. словами, анаморфизм генерирует развесистую структуру данных из входного значения)

Аналогичные по смыслу функции можно написать для более сложных структур данных. Их можно даже получать автоматически (см. статью о бананах в космосе).

Здравствуйте, palm mute, Вы писали:

PM> (см. статью о бананах в космосе).

всего 5 сек

Здравствуйте, deniok, Вы писали:

PM>> (см. статью о бананах в космосе).
D>всего 5 сек

почти

. правильная ссылка: http://citeseer.ist.psu.edu/293490.html

Здравствуйте, palm mute, Вы писали:

PM>почти

. правильная ссылка: http://citeseer.ist.psu.edu/293490.html

Гм. Это у функциональшиков фишка такая что-ли — страницы наоборот?

Здравствуйте, EvilChild, Вы писали:

EC>Здравствуйте, Кодт, Вы писали:

К>>Для любителей теории нужно вспомнить про ххххх-морфизмы и прочесть труд "Линзы, бананы и разлохмаченные провода".
EC>А можно пару примеров ххххх-морфизмов из жизни? Труд ниасилил.

Катаморфизм — это сворачивание структуры.

Вместо каждого конструктора ( : ) подставляем двухместную функцию, а вместо конструктора [] — нульместную (т.е. значение)
Пример 1: сумма

sum [] = 0
sum (x : xs) = x + sum xs

sum xs = foldr (+) 0 xs

Пример 2: длина

length [] = 0
length (_ : xs) = 1 + length xs

length xs = foldr (\x y -> 1 + y) 0 xs

(на самом деле, и сумму, и длину лучше вычислять энергично, с помощью foldl' — но это в силу ассоциативности и коммутативности операции сложения).

Всякую-разную арифметику — цепные дроби, например — тоже можно сюда отнести.

-- цепная дробь
-- chain [a,b,c,d] = a+1/(b+1/(c+1/(d)))
chain xs = result
    where
        (Just result) = foldr f t
        t = Nothing -- терминальное значение
        f x Nothing = Just x -- обрабатываем последнее значение
        f x (Just y) = Just (x + 1/y) -- обрабатываем результат рекурсии

-- схема Горнера для многочленов
-- horner x [a,b,c,d] = a + bx + cxx + dxxx = a+x*(b+x*(c+x*(d+x*0)))
horner x coeffs = foldr (\c p -> c+x*p) 0 coeffs

Как, кстати, и фильтры — вообще-то, это уже хиломорфизмы (превращающие один список в другой)

-- берём голову списка, до тех пор, пока предикат выполняется
takeWhile predicate xs = foldr f [] xs
    where
        f x rest = if predicate x then (x : rest) else []

-- оставляем только те элементы списка, для которых предикат выполняется
filter predicate xs = foldr f [] xs
    where
        f x rest = if predicate x then (x : rest) else rest
        -- или, с каррингом,
        f x = if predicate x then (x:) else id

Анаморфизм — это порождение структуры из затравки.

Есть некая затравка; функция, порождающая из затравки аргументы для конструктора : и продолжения, либо признак остановки (нуль аргументов для конструктора [])

Сам комбинатор выглядит так

unfoldr f x0 = -- штатный
    case (f x0) of
        Nothing -> []
        | Just (y0, x1) -> y0 : unfoldr f x1

-- аналогично, для дерева с нуль-листьями
data BinTree0 a = BTNull | BTNode a (BinTree0 a) (BinTree0 a)

-- для простоты, используем всё тот же вариантный тип Maybe
unfoldBT0 f x0 =
    case (f x0) of
        Nothing -> BTNull
        | Just (y0,x1,x2) -> BTNode y0 (unfoldBT0 f x1) (unfoldBT0 f x2)

-- для дерева с тремя типами узлов (нуль-листья, листья с данными, узлы с ключами)
data BinTree1 a b = BTNull | BTLeaf a | BTNode a (BinTree1 a b) (BinTree1 a b)

-- здесь уже нужен трёхвариантный тип - например, комбинация из Maybe и Either
unfoldBT1 f x0 =
    case (f x0) of
        Nothing -> BTNull
        | Just (Left y) -> BTLeaf y
        | Just (Right (z,x1,x2)) -> BTNode z (unfoldBT1 f x1) (unfoldBT2 f x2)

Примеры

iterate f x0 = unfoldr (\x -> Just (x, f x)) x0
    -- порождает бесконечный (ленивый) список: [x0, f(x0), f(f(x0)), ...]

tails xs = unfoldr f x0 where -- список суффиксов (применяем функцию tl до упора)
    f xs = if null xs then Nothing else Just (xs, tl xs)

iterWhile p f x0 = unfoldr (\x -> if p x then Just (f x) else Nothing) x0
    --     порождает список, останавливающийся по условию
    --     то же самое можно выразить и так:
iterWhile p f x0 = takeWhile p $ iterate f x0

Последний пример демонстрирует сплавление (fusion) морфизмов.

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Gaperton, Вы писали:

G>Эрланг — говно тормозное.
Если есть желание пошутить, то делайте пожалуйста это в специально отведённом для этого месте.
Здесь подобные сообщения могут быть рассмотрены только как провокация. Вполне удачная.

... << RSDN@Home 1.2.0 alpha rev. 749>>

Здравствуйте, frogkiller, Вы писали:

F>Похоже, так никто шутку и не оценил

эта шутка уже всех задолбала

... << RSDN@Home 1.2.0 alpha rev. 745>>

Здравствуйте, palm mute, Вы писали:

PM>почти

. правильная ссылка: http://citeseer.ist.psu.edu/293490.html

Эх, всё-таки жалко, что в хаскеле отказались от гоферовского обобщения: map и ++ стали операциями только над списками, а обобщённые операции теперь называются fmap и mplus соответственно.
Ну зачем они это сделали? Было так красиво и прикольно...

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Кодт, Вы писали:

К>Эх, всё-таки жалко, что в хаскеле отказались от гоферовского обобщения: map и ++ стали операциями только над списками, а обобщённые операции теперь называются fmap и mplus соответственно.
К>Ну зачем они это сделали? Было так красиво и прикольно...

Видимо, боялись отпугнуть новичков — излишне полиморфный код порождает устрашающие сообщения об ошибках. AFAIK, по этой же причине отказались от monad comprehensions в пользу list comprehensions.

Стандартная Прелюдия довольно часто вызывает дебаты, есть куча предложений по ее реформе; для коллекций есть альтернативные библиотеки. См.
http://hackage.haskell.org/trac/ghc/attachment/wiki/CollectionClassFramework/Collections.hs
или
http://software.complete.org/listlike/static/doc/, например (DISCLAIMER: я сам с ними не разбирался, когда понадобился класс, унифицирующий подмножество интерфейсов String и ByteString, быстро и грязно слепил сам).

К>Для любителей теории нужно вспомнить про ххххх-морфизмы и прочесть труд "Линзы, бананы и разлохмаченные провода".
barbed wire — разве не колючая проволока?

Здравствуйте, <Аноним>, Вы писали:

А>barbed wire — разве не колючая проволока?
О! Спасибо! Буду знать.

... << RSDN@Home 1.2.0 alpha rev. 655>>

G>Эрланг — говно тормозное. Ну? Кто бежит меня арестоффать? Эй, Мамут? Ты там как, нормально пережил неконструктивную критику?

Пааапрашу доказательства в студию! (только IO не трогать

)

Здравствуйте, Mamut, Вы писали:

G>>Эрланг — говно тормозное. Ну? Кто бежит меня арестоффать? Эй, Мамут? Ты там как, нормально пережил неконструктивную критику?

M>Пааапрашу доказательства в студию! (только IO не трогать

)

http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=hipe&lang2=scala
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=hipe&lang2=sbcl

всё дело в сообщениях..

Здравствуйте, Аноним, Вы писали:

G>>>Эрланг — говно тормозное. Ну? Кто бежит меня арестоффать?

А>всё дело в сообщениях..

на этот раз Гапертон предусмотрительно зашёл Анонимом

Здравствуйте, BulatZiganshin, Вы писали:

G>>>>Эрланг — говно тормозное. Ну? Кто бежит меня арестоффать?
А>>всё дело в сообщениях..
BZ>на этот раз Гапертон предусмотрительно зашёл Анонимом

Гапертон никогда не заходит Анонимом

. Но это идея

.

Здравствуйте, Mamut, Вы писали:

G>>Эрланг — говно тормозное. Ну? Кто бежит меня арестоффать? Эй, Мамут? Ты там как, нормально пережил неконструктивную критику?

M>Пааапрашу доказательства в студию! (только IO не трогать

)

Ну вообще это была шутка, потому как мы то с тобой знаем, что Эрланг в сто раз круче Немерле и вообще лучший в мире язык (за неконструктивную похвалу еще не сажают тут, интересно? Надо проверить), но раз ты просишь, то мы завсегда найдем пару лопат дегтя.
1. Конечно же, IO. Стыдно иметь до такой степени тормозной IO. Могли бы его целиком в нативе реализовать, в конце концов.
2. Любой алгоритм, заточенный под применение массивов данных, будет ацки тормозить. В Эрланге чудавищная поддержка массивов — там даже на туплах их делать неудобно — нет операции bulk update для туплов. Приходится применять таблицы ets (обязательное копирование как при чтении, так и при записи, плюс они не гарбаджколлектятся, руками их надо удалять и создавать) либо словарь процесса (это эффективнее, но надо сказать дазвиданье изоляции и свободному повторному использованию кода — либо придется завернуть все в процесс, и налететь на передачу сообщений, что сводит на ноль весь трюк).
3. Строки на списках занимают в 8 раз больше памяти и они тормознее. Приходится применять для строк бинарисы, чтобы работало сносно, а это не слишком удобно. Да и строковых функций на бинарисах в стандартной либе нет.
4. Мнезия тормозит на больших таблицах — она проектировалась для задач in-memory database.
5. native-компилятор типа есть, но его нельзя применять в продакшн-системах, так как он не поддерживает динамической отгрузки кода.

G>Ну вообще это была шутка, потому как мы то с тобой знаем, что Эрланг в сто раз круче Немерле и вообще лучший в мире язык (за неконструктивную похвалу еще не сажают тут, интересно? Надо проверить), но раз ты просишь, то мы завсегда найдем пару лопат дегтя.

Буедм надеятся, что с помощью EEP можно будет некоторые из этих лопат нейтрализовать

Здравствуйте, Gaperton, Вы писали:

G>Здравствуйте, Mamut, Вы писали:

G>>>Эрланг — говно тормозное. Ну? Кто бежит меня арестоффать? Эй, Мамут? Ты там как, нормально пережил неконструктивную критику?

M>>Пааапрашу доказательства в студию! (только IO не трогать

)
G>Ну вообще это была шутка, потому как мы то с тобой знаем, что Эрланг в сто раз круче Немерле и вообще лучший в мире язык (за неконструктивную похвалу еще не сажают тут, интересно? Надо проверить), но раз ты просишь, то мы завсегда найдем пару лопат дегтя.
G>1. Конечно же, IO. Стыдно иметь до такой степени тормозной IO. Могли бы его целиком в нативе реализовать, в конце концов.
По поводу этого пункта вот недавно обсуждали в мейллисте очередной "тест" и Клаке привёл вот это

G>>1. Конечно же, IO. Стыдно иметь до такой степени тормозной IO. Могли бы его целиком в нативе реализовать, в конце концов.
К>По поводу этого пункта вот недавно обсуждали в мейллисте очередной "тест" и Клаке привёл вот это

По поводу IO сейчас активная полемика развернулась. Полная история здесь: http://erlang.dmitriid.com/news/item/97

	От:	mini_root_2
	Дата:	17.09.07 06:04
	Оценка:

	От:	Andy Panda
	Дата:	17.09.07 06:44
	Оценка:

	От:	deniok
	Дата:	17.09.07 07:19
	Оценка:

	От:	BulatZiganshin
	Дата:	17.09.07 09:54
	Оценка:

	От:	mini_root_2
	Дата:	17.09.07 09:57
	Оценка:

От:	Andrei N.Sobchuck	www.smalltalk.ru
Дата:	19.09.07 08:11
Оценка:

	От:	Блудов Павел
	Дата:	19.09.07 10:48
	Оценка:

От:	Gaperton	http://gaperton.livejournal.com
Дата:	19.09.07 13:09
Оценка:	+3

	От:	Vermicious Knid
	Дата:	19.09.07 14:53
	Оценка:	33 (1) +1

	От:	palm mute
	Дата:	19.09.07 17:23
	Оценка:	19 (2)

От:	Odi$$ey	http://malgarr.blogspot.com/
Дата:	20.09.07 03:55
Оценка:	+4 -1

От:	Mamut	http://dmitriid.com
Дата:	24.09.07 16:36
Оценка:

От:	Курилка	http://kirya.narod.ru/
Дата:	28.09.07 07:01
Оценка:

	От:	frogkiller
	Дата:	18.09.07 09:31
	Оценка:

	От:	Кодт
	Дата:	18.09.07 11:51
	Оценка:

	От:	z00n
	Дата:	18.09.07 17:58
	Оценка:

	От:	Аноним
	Дата:	23.09.07 21:25
	Оценка:	+3