lomeo: (лямбда)
[personal profile] lomeo
Я это как-то писал, но напишу ещё раз, бо тема поднялась.

Недостатки явной рекурсии по сравнению с комбинаторами (ага, zip3):

  • Рекурсия непонятна (согласен, это субъективное).
  • Обычно используется с декомпозицией, нарушая инкапусляцию.
  • Всегда используется для работы с элементами, вместо работы с коллекцией (wholemeal programming).
  • Цепочка вызовов проще для оптимизации.
  • Сложнее нежно мною любимый equational reasoning.

Юный хаскеллист, избегай явной рекурсии!

Ну и ссылочка, куда без неё!

Date: 2012-11-30 01:53 pm (UTC)
From: [identity profile] inv2004.livejournal.com
Могу только поддержать.

Date: 2013-10-04 05:24 pm (UTC)
From: [identity profile] mrparker.livejournal.com
Могу только плюсанутся...

Date: 2012-11-30 01:56 pm (UTC)
From: [identity profile] nealar.livejournal.com
Когда сложность кода - уровня хелловорда, рекурсия понятна. А когда его становится побольше, уже надо спасаться комбинаторами.

Date: 2012-11-30 02:27 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Я стараюсь использовать её для реализации комбинаторов. Ну, т.е. вот есть модуль с объявленным типом, сначала, конечно typeclass morphism, потом более конкретные функции для этого типа. И вот всё это можно и через рекурсию. А наружу уходят чистые комбинаторы.

Date: 2012-11-30 03:45 pm (UTC)
From: [identity profile] thedeemon.livejournal.com
>сначала, конечно typeclass morphism

Вот об этом было бы интересно подробнее послушать.

Date: 2012-11-30 03:58 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Да собственно тут (http://conal.net/papers/type-class-morphisms/) всё сказано.

Зачем нам алгебраические структуры в самом деле? Чтобы их использовать! :-)

Ну, и в нагрузку ещё немножко про дизайн (http://lukepalmer.wordpress.com/2008/07/18/semantic-design/) от Люка Палмера (правда, это оффтопик).

Date: 2012-11-30 04:07 pm (UTC)
From: [identity profile] thedeemon.livejournal.com
Первое я видел, но хотелось бы примеров из личной практики.

(no subject)

From: [identity profile] lomeo.livejournal.com - Date: 2012-11-30 05:18 pm (UTC) - Expand

(no subject)

From: [identity profile] thedeemon.livejournal.com - Date: 2012-11-30 05:42 pm (UTC) - Expand

(no subject)

From: [identity profile] nivanych.livejournal.com - Date: 2012-12-01 07:09 am (UTC) - Expand

Date: 2012-11-30 04:48 pm (UTC)
From: [identity profile] miserakl.livejournal.com
> Ну и ссылочка, куда без неё!

Кажется, ссылка потерялась, и ЖЖ вместо неё подставил адрес текущей страницы.

Date: 2012-11-30 05:20 pm (UTC)
From: [identity profile] lomeo.livejournal.com
:-) Явная рекурсия - зло.

Date: 2012-11-30 06:45 pm (UTC)
From: [identity profile] miserakl.livejournal.com
А, так это специально. Небось до вечера пятницы тоже нарочно откладывали? :)

Date: 2012-11-30 07:06 pm (UTC)
From: [identity profile] nealar.livejournal.com
Отложенные вычисления :)

(no subject)

From: [identity profile] miserakl.livejournal.com - Date: 2012-12-01 01:04 pm (UTC) - Expand

(no subject)

From: [identity profile] lomeo.livejournal.com - Date: 2012-12-01 05:30 pm (UTC) - Expand

Date: 2012-11-30 07:14 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Нет, так вышло ;-)

И можно на ты.

Date: 2012-11-30 08:03 pm (UTC)
From: [identity profile] nivanych.livejournal.com
Можно ещё такой довод.
Структурная рекурсия, это один простой паттерн, легко укладывающийся в довольно простой Тьюринг-худой язык.
А значит, имеем простой и предсказуемый reasoning.
Что вполне подтверждается на практике.
Общая рекурсия заставляет думать в рамках уже Тьюринг-полноты, что в общем случае, неразрешимо даже теоретически, а не то, чтобы уложилось человеку в голову.
Конечно же, при реальном программировании, возникает ряд "паттернов" (навроде отслеживания разборки значения индуктивного типа), иначе бы было очень сложно сделать что-то.
Ну вот, структурная рекурсия, это один из таких паттернов — простой, чОтко формализованный и весьма общий.

Date: 2012-11-30 08:55 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Один раз реализовать свёртку полезно для типа ;-) Хотя сейчас уже deriving Foldable есть.

Date: 2012-12-01 07:22 am (UTC)
From: [identity profile] nivanych.livejournal.com
> полезно для типа

Ему от этого становится лучше, да! ;-)

Date: 2012-11-30 08:39 pm (UTC)
From: [identity profile] swizard.livejournal.com
А можно вот такой теоретический вопрос: как предлагается заменять, например, двойную (или более широкую) рекурсию комбинаторами?

Date: 2012-11-30 09:05 pm (UTC)
From: [identity profile] lomeo.livejournal.com
1. "Избегайте" /= "Никогда не используйте".
2. Этот пост возник из-за этой дискуссии (http://levgem.livejournal.com/420910.html?thread=5124654#t5124654). Т.е. "как заменить" уже есть.

Не стоит заменять. Если нужно, скажем, делать разбор двух структур по условию, то я пишу рекурсивный код. Пример: merge двух сортированных списков.

Date: 2012-11-30 09:54 pm (UTC)
From: [identity profile] swizard.livejournal.com
Понятно, спасибо.

Date: 2012-11-30 09:31 pm (UTC)
From: [identity profile] thesz.livejournal.com
А что это такое?

В качестве возможного примера могу предложить Omega monad: http://hackage.haskell.org/package/control-monad-omega

Комбинатор рекурсивной обработки потенциально бесконечных списков с гарантированным перечислением всех элементов.

Date: 2012-11-30 09:53 pm (UTC)
From: [identity profile] swizard.livejournal.com
Ну, я могу навскидку привести вот такую задачу: есть схема проекта в виде дерева зависимостей, вот в таком виде:



Где, грубо говоря, file -- это исходник, а module -- директория. Нужно написать функцию, которая применит функцию компиляции к каждому исходному файлу, причём в правильном порядке, с учётом что от чего зависит.

Для данного примера порядок может быть таким: f1, f2, f4, f5, f3, f6, f0, f7.

В идеале ещё бы обнаружить циклические зависимости.

Как это сделать двойной рекурсией -- очевидно, а вот комбинаторного решения я придумать не могу.

Date: 2012-11-30 10:09 pm (UTC)
From: [identity profile] thesz.livejournal.com
Scrap your boilerplate.

http://www.haskell.org/haskellwiki/Scrap_your_boilerplate

(есть ещё более навороченные и/или удобные варианты, более поздние)

Например, одной строкой можно получить все файлы. Другой - все зависимости. Отображение (map compile) на файлы даст компиляцию и тп.

Наверное, это ближе всего к нужному тебе.

(no subject)

From: [identity profile] swizard.livejournal.com - Date: 2012-11-30 10:27 pm (UTC) - Expand

(no subject)

From: [identity profile] swizard.livejournal.com - Date: 2012-11-30 10:28 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2012-11-30 10:42 pm (UTC) - Expand

(no subject)

From: [identity profile] swizard.livejournal.com - Date: 2012-11-30 10:59 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2012-11-30 11:33 pm (UTC) - Expand

(no subject)

From: [identity profile] voidex.livejournal.com - Date: 2012-12-01 02:39 am (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2012-12-01 10:54 am (UTC) - Expand

(no subject)

From: [identity profile] voidex.livejournal.com - Date: 2012-12-01 11:59 am (UTC) - Expand

(no subject)

From: [identity profile] swizard.livejournal.com - Date: 2012-12-01 11:06 am (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2012-12-01 12:03 pm (UTC) - Expand

(no subject)

From: [identity profile] rigidus.livejournal.com - Date: 2012-12-03 04:10 pm (UTC) - Expand

(no subject)

From: [identity profile] some41.livejournal.com - Date: 2012-12-01 04:05 am (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2012-12-01 10:53 am (UTC) - Expand

(no subject)

From: [identity profile] some41.livejournal.com - Date: 2012-12-01 10:47 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2012-12-01 11:00 pm (UTC) - Expand

(no subject)

From: [identity profile] some41.livejournal.com - Date: 2012-12-01 11:34 pm (UTC) - Expand

Date: 2012-11-30 11:51 pm (UTC)
From: [identity profile] thesz.livejournal.com
Что-то мне вспомнилось, что у Луговского, что ли, была либа на Лиспе а-ля SYB. Для работы с языками и их трансляцией.

Он на ней деньги собирался зарабатывать. ;)

Date: 2012-12-01 12:17 am (UTC)
From: [identity profile] voidex.livejournal.com
Ну придумать-то можно, вопрос в том, будет ли это понятнее, чем рекурсия в данном случае.
Идея такая:
1. Строим список пар (имя объекта, непосредственные зависимости). Для файла это зависимости, для модуля - имена компонентов.
2. Строим дерево зависимостей, т.е. разворачиваем непосредственные зависимости.
3. Сортируем очевидным образом (зависящий идёт позже, если независимы - по имени)
4. Вуаля

Код без учёта циклических зависимостей: http://hpaste.org/78574

Для учёта идея проста, мы храним "родителей" и смотрим, чтобы текущий от них не зависел: http://hpaste.org/78575

Update

Я был не прав в пункте 3, сортировать не нужно. Вот конечный результат: http://hpaste.org/78585
Edited Date: 2012-12-01 06:05 am (UTC)

(no subject)

From: [identity profile] nivanych.livejournal.com - Date: 2012-12-01 09:50 am (UTC) - Expand

(no subject)

From: [identity profile] swizard.livejournal.com - Date: 2012-12-01 11:13 am (UTC) - Expand

(no subject)

From: [identity profile] some41.livejournal.com - Date: 2012-12-01 10:42 pm (UTC) - Expand

Date: 2012-12-01 11:11 am (UTC)
From: [identity profile] lomeo.livejournal.com
Тип содрал у [livejournal.com profile] voidex, решение простое: использовать графы и uniplate для выдёргивания всего (аналог listify у [livejournal.com profile] thesz). Циклы не проверял.

http://hpaste.org/78589 (http://hpaste.org/78589)

(no subject)

From: [identity profile] nponeccop.livejournal.com - Date: 2012-12-01 08:38 pm (UTC) - Expand

(no subject)

From: [identity profile] nponeccop.livejournal.com - Date: 2012-12-01 10:57 pm (UTC) - Expand

(no subject)

From: [identity profile] lomeo.livejournal.com - Date: 2012-12-02 04:03 am (UTC) - Expand

Date: 2012-12-01 10:25 pm (UTC)
ext_659502: (полосатая свинья)
From: [identity profile] some41.livejournal.com
для красивых комбинаторных решений часто приходится напрячься и переосмыслить задачу в более общих терминах, чтобы то, что мы хотим было частным случаем какой-то общей операции, может над чуть более общей структурой данных.
но для того, чтобы избежать явной рекурсии это не обязательно. например, в данном случае берем рекурсивный алгоритм из википедии (http://en.wikipedia.org/wiki/Topological_sort, второй) и пишем его в лоб: http://hpaste.org/78601
основная функция получилась так:
topsort cm = fst $ foldr visit ([],S.empty) roots
    where roots = M.elems $ cm `diff` allDepends cm
	  visit n (rs,seen) = if name n `S.member` seen then (rs,seen)
	                      else (rs' ++ [n],seen')
			          where (rs',seen') = foldr visit (rs,S.insert (name n) seen) (deps n)
	  deps File{ dependsOn=ds }    = find ds
	  deps Module{ components=cs } = cs
	  find = map (\name -> fromJust $ M.lookup name cm)

Код сурово императивный, что видно по foldr, но хотя бы нет явной структурной рекурсии.
Как известно, вместо рекурсии можно использовать цикл с очередью (http://hpaste.org/78602):
topsort cm = res
    where roots = M.elems $ cm `diff` allDepends cm
	  visit n (qs,rs,seen) = if name n `S.member` seen then (qs,rs,seen)
	                         else (qs ++ deps n, n:rs, S.insert (name n) seen)
	  deps File{ dependsOn=ds }    = find ds
	  deps Module{ components=cs } = cs
	  find = map (\name -> fromJust $ M.lookup name cm)
	  next (qs,rs,seen) = foldr visit ([],rs,seen) qs
	  (_,res,_) = until (\(qs,_,_) -> null qs) next (roots,[],S.empty)

Код по-прежнему императивный, но явной рекурсии больше нет. Она спрятана в until и foldr.

Если все немного обобщить (разрешить зависимости и на уровне модулей, чтобы структура была более симметричная) и причесать, то можно избавиться от рекурсии и во flatten, перенеся ее в общий комбинатор foldTree: http://hpaste.org/78603

Profile

lomeo: (Default)
Dmitry Antonyuk

December 2015

S M T W T F S
  12345
6789101112
131415 16171819
20212223242526
2728293031  

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 24th, 2017 03:48 pm
Powered by Dreamwidth Studios