LINUX.ORG.RU

Haskell и Foldable

 ,


1

4

Всем привет.

Познаю хаскель, наткнулся на проблему.

Есть простое дерево с лесом:

data RoseTree a = RoseEmpty | RoseTree a [RoseTree a]                                  
                    deriving (Show,Eq)

Пытаюсь реализовать для него интерфейс тайпкласса Foldable:

instance Foldable RoseTree where                                                       
    foldr _ acc RoseEmpty       = acc                                           
    foldr f acc (RoseTree x []) = f x acc                                       
    foldr f acc (RoseTree x ts) = let mapped    = map (foldr f acc) ts          
                                      folded    = foldr f acc mapped            
                                  in f x folded

Идея простая: чтобы свернуть список поддеревьев, применяю частично примененный (foldr f acc) к списку, получаю вместо списка поддеревьев (RoseTree a) список значений (a), потом сворачиваю список значений и применяю функцию f к значению ноды из паттерна и свернутому значению поддеревьев.

Но получаю ошибку в ghci:

error:
    • Couldn't match type ‘b’ with ‘a’
      ‘b’ is a rigid type variable bound by
        the type signature for:
          foldr :: forall a b. (a -> b -> b) -> b -> RoseTree a -> b
        at lecture11.hs:131:5
      ‘a’ is a rigid type variable bound by
        the type signature for:
          foldr :: forall a b. (a -> b -> b) -> b -> RoseTree a -> b
        at lecture11.hs:131:5
      Expected type: [a]
        Actual type: [b]
    • In the third argument of ‘foldr’, namely ‘mapped’
      In the expression: foldr f acc mapped
      In an equation for ‘folded’: folded = foldr f acc mapped
    • Relevant bindings include
        folded :: b (bound at lecture11.hs:134:39)
        mapped :: [b] (bound at lecture11.hs:133:39)
        ts :: [RoseTree a] (bound at lecture11.hs:133:29)
        x :: a (bound at lecture11.hs:133:27)
        acc :: b (bound at lecture11.hs:133:13)
        f :: a -> b -> b (bound at lecture11.hs:133:11)

Насколько я понимаю, ругань на то, что частично примененный (foldr f acc) получает на вход список не того типа. Но не могу понять почему, ведь этот foldr есть мой рекурсивный вызов и по идее он должен выглядеть так:

map (foldr f acc) ts

или для примера

map (foldr (+) 0) [RoseTree 1 [], RoseTree 2 [], RoseTree 3 []]

т.е.

[foldr (+) 0 (RoseTree 1 []), foldr (+) 0 (RoseTree 2 []), foldr (+) 0 (RoseTree 3 [])]

и по одной из моих реализаций Foldable RoseTree, где

foldr f acc (RoseTree x []) = f x acc

, получаем [1, 2, 3], что подтверждается пошаговым биндингом этого кода в ghci, но вот целиком ghci мой Foldable не проглатывает.

В чем проблема, парни?

или для примера

Возьми для примера функцию с разными аргументами. Например f x y = length x + y.

map (foldr f 0) [RoseTree "1" [], RoseTree "2" [], RoseTree "3" []]

получишь [1, 1, 1]. И его попытаешься скормить в foldr f 0 [1,1,1]. Но f не может получить из списка число, так как хочет строку. Ой.

monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 1)
instance Foldable RoseTree where                                                
    foldr _ acc RoseEmpty       = acc                                           
    foldr f acc (RoseTree x []) = f x acc                                       
    foldr f acc (RoseTree x ts) = f x (foldr (flip (foldr f)) acc ts)

Типизацию проходит, скорее всего правильно, дальше думать лень. Проверь сам.

Crocodoom ★★ ()

Что такое по сути foldr? Это замена n-арных конструкторов данных на n-арные функции.

Тип foldr для твоего дерева (использую твои обозначения):

foldr :: (a -> b -> b) -> b -> RoseTree a -> b
f :: a -> b -> b
acc :: b

Твоё дерево выглядит как

RoseTree a = RoseTree a (RoseTree a : RoseTree a : RoseTree a : ... : RoseTree a : [])
Тут второе слово RoseTree — это конструктор, остальные — имя типа. Можно запутаться, но что поделать.

У нас три конструктора под замену: RoseTree, (:) и []. Заменять должны на подходящие по арности и типам функции. И в результате должен получиться тип b.

Очевидно, что конструктор RoseTree надо заменить на f. А вот дальше возникают сложности. Обозначим пока замену (:) как ?, а замену [] как ??

b = f a (RoseTree a ? RoseTree a ? RoseTree a ? ... ? RoseTree a ? ??)

Т.к. второй аргумент у f имеет тип b, значит ? должен возвращать тип b. И первым аргументом ? должен принимать тип RoseTree a. То есть

? :: RoseTree a -> c -> b

Тип c мы пока не знаем. Подумаем, на что мы можем заменить ??. Это нуль-арный конструктор, значит мы его должны заменить на какую-то константу. Константа у нас по сути одна, это acc.

Значит ?? = acc и ?? :: b. Отсюда моментально получаем, что c = b.

Значит

? :: RoseTree a -> b -> b

Только одна функция имеет такой тип, это flip (foldr f). Теперь мы готовы делать foldr:

b = f a (RoseTree a `flip (foldr f)` RoseTree a `flip (foldr f)` RoseTree a `flip (foldr f)` ... `flip (foldr f)` RoseTree a `flip (foldr f)` acc)

Осталось свернуть этот паровоз в скобках в обычный foldr (уже для списков! не для дерева), собственно и получаем

f x (foldr (flip (foldr f)) acc ts)
Crocodoom ★★ ()
Последнее исправление: Crocodoom (всего исправлений: 1)
Ответ на: комментарий от Crocodoom

Очевидно, что конструктор RoseTree надо заменить на f. А вот дальше возникают сложности. Обозначим пока замену (:) как ?, а замену [] как ??

Вот это тоже верное решение:

instance Foldable RoseTree where
    foldr _ acc RoseEmpty       = acc
    foldr f acc (RoseTree x []) = f x acc
    foldr f acc (RoseTree x ts) = foldr (flip (foldr f)) (f x acc) ts

Так что не очевидно.

monk ★★★★★ ()
Ответ на: комментарий от monk

Ваш пример проходит компиляцию, однако не «заменяет n-арные конструкторы данных на n-арные функции», а именно этим должен заниматься foldr.

Если развернуть значение RoseTree x ts в граф конструкторов, то на какую именно бинарную функцию вы заменили самый верхний конструктор RoseTree?

Crocodoom ★★ ()
Ответ на: комментарий от Crocodoom

Типизацию проходит, скорее всего правильно, дальше думать лень.

Вот именно за эту идею я не люблю Хаскел. Точнее тех, кто его продвигает, как язык, на котором пишущий делает меньше ошибок.

monk ★★★★★ ()
Ответ на: комментарий от Crocodoom

Ваш пример проходит компиляцию, однако не «заменяет n-арные конструкторы данных на n-арные функции», а именно этим должен заниматься foldr.

Где написано, что он должен делать именно это? То есть, по-Вашему, для post-order поиска дерево обязано быть описано как data RoseTree a = RoseEmpty | RoseTree [RoseTree a] a.

А как, по-Вашему, должно выглядеть дерево, которое fold должен обходить в ширину? То есть, foldr (:) [] tree должно вернуть список, где будет сначала вершина, затем вершины в уздах первого уровня, затем — второго и так далее.

monk ★★★★★ ()
Ответ на: комментарий от Crocodoom

Ваш пример проходит компиляцию, однако не «заменяет n-арные конструкторы данных на n-арные функции», а именно этим должен заниматься foldr.

Попробуй так написать foldr для реализации очереди:

data Queue a = Queue { 
  inbox :: [a], 
  outbox :: [a] 
} deriving (Eq, Show)

push :: a -> Queue a -> Queue a
push e (Queue inb out) = Queue (e:inb) out

pop :: Queue a -> (a, Queue a)
pop q@(Queue inb []) = pop $ Queue [] (reverse inb)
pop (Queue inb outb) = (head outb, Queue inb (tail outb))

monk ★★★★★ ()
Ответ на: комментарий от monk

Где написано, что он должен делать именно это? То есть, по-Вашему, для post-order поиска дерево обязано быть описано как data RoseTree a = RoseEmpty | RoseTree [RoseTree a] a.

А как, по-Вашему, должно выглядеть дерево, которое fold должен обходить в ширину? То есть, foldr (:) [] tree должно вернуть список, где будет сначала вершина, затем вершины в уздах первого уровня, затем — второго и так далее.

Возможно, я не прав. Но что тогда, по вашему, означает подчеркнутая фраза?

toList :: t a -> [a]

List of elements of a structure, from left to right

Я объясню двумя строчками кода, как понимал её я

λ> let t = RoseTree "1" [RoseTree "2" [RoseTree "3" [], RoseTree "4" []], RoseTree "5" [RoseTree "6" [], RoseTree "7" []]]
λ> toList t
["1","2","3","4","5","6","7"]

Как можно видеть, toList выдал в точности такой же порядок элементов, который получается при чтении t слева направо.

«Мой» foldr именно такое поведение toList и обеспечивает.

Если «ваш» foldr будет сворачивать t как-то по-другому, то и порядок в toList получится перемешанный. Тогда в чём же будет соблюдение этого from left to right?

Crocodoom ★★ ()
Ответ на: комментарий от Crocodoom

Для дерева в общем случае нет понятия слева направо. Есть в глубину, в ширину, сверху и снизу. А слева направо есть у линеаризации дерева, которая зависит от порядка обхода.

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

      4
|-----|-----|
1     5     7
|   |----|
2   3    6

monk ★★★★★ ()
Ответ на: комментарий от Crocodoom

Как можно видеть, toList выдал в точности такой же порядок элементов, который получается при чтении t слева направо.

Для

data Queue a = Queue { 
  outbox :: [a], 
  inbox :: [a] 
}

toList (Queue x y) = y ++ reverse x
а не [x, y] или x ++ y

monk ★★★★★ ()
Ответ на: комментарий от monk

Речь идёт не об обходе дерева в смысле RoseTree, а об обходе дерева в смысле дерева конструкторов некоторого типа. Дерево конструкторов любого данных можно записать в строчку (и именно так мы и задаем их в хаскеле), и эту строчку можно прочитать слева направо.

Вместо RoseTree я могу поставить какой угодно конструктор, или даже разные конструкторы (допустим у нас такой вот страшный тип данных с кучей конструкторов).

Смотрите:

λ> let t = A "1" [B "2" [C "3" [], D "4" []], E "5" [F "6" [], G "7" []]]
λ> toList t
["1","2","3","4","5","6","7"]

Тут вообще не важно, что такое эти A, B, C, ... Но если есть инстанс Foldable для этого типа, то toList t обязан возвращать ["1","2","3","4","5","6","7"]. Вот так я понимаю фразу

List of elements of a structure, from left to right

Crocodoom ★★ ()
Последнее исправление: Crocodoom (всего исправлений: 1)
Ответ на: комментарий от Crocodoom
data Queue a = Queue { 
  outbox :: [a], 
  inbox :: [a] 
} deriving (Eq, Show)

push :: a -> Queue a -> Queue a
push e (Queue out inb) = Queue out (e:inb) 

pop :: Queue a -> (a, Queue a)
pop q@(Queue [] inb) = pop $ Queue (reverse inb) []
pop (Queue outb inb) = (head outb, Queue (tail outb) inb)

emptyQ = Queue [] []

Чему должен быть равен

x = push 3 $ push 2 emptyQ 
toList x

y = snd. pop $ push 3 $ push 2 $ push 1 emptyQ
toList y
?

Элементы в очереди они и те же: fst . pop x = fst . pop y, fst . pop $ snd . pop x = fst . pop $ snd . pop y и т.д.

monk ★★★★★ ()
Ответ на: комментарий от monk

Про data Queue отвечу вам завтра. А вы пока напишите, какой смысл Вы вкладываете в ремарку к toList "List of elements of a structure, from left to right.". Если речь идёт не об обходе строчной записи дерева конструкторов слева направо, тогда о чём? Какая-то же семантика должна быть заложена.

Crocodoom ★★ ()
Ответ на: комментарий от monk

поддержу Crocodoom. Есть учебник под рукой, недавно читал, поэтому могу дать ссылку прямо на страницу, Graham Hutton, Programming in Haskell, 2nd edition, стр 79 имеет такое предложение:

More generally, the behaviour of foldr can be summarised as follows:

foldr (#) v [x0,x1,...,xn] = x0 # (x1 # (... (xn # v)...))

так же об этом есть упоминание на стр. 202 той же книги (evaluating of foldr... performed from right-to-left)

Т.е. такое понимание как минимум встречается в литературе. Правда, такого (про конструкторы) я не встечал объяснения как дал крокодум.
На сколько я себе представлял дело в ассоциативности, как в цитате выше из хаттона. В подтверждение что такое представление существует не только у хаттона, могу привести цитату из хаскель-вики

https://wiki.haskell.org/Fold

either by recursively combining the first element with the results of combining the rest (called a right fold)

т.е. решение которое дал крокодум соотвествует этим объяснениям.

Я бы сказал надо начинать с самого последнего дерева в списке, взяв самое последнее дерево в его списке (если существует) и т.д. до последнего дерева в последнем списке, затем предпоследнее дерево в последнем списке.. затем предпоследний список и т.д назад. И это будет соответствовать правой ассоциативности.

Что до аргумента про свёртку (обычного) дерева, там можно реализовывать фолдр по разному. Но в целом кажется что не каждая реализация будет соотвествовать семантике фолдр (то есть правоассоциативности). Кажется что другие названия для свёрток в случае если они не точно соотвесвтуют foldr были бы более кстати. Но я не готов тут спорить, может они кстати и существуют.

Что до аргумента «делают меньше ошибок на хаскеле» - так до этого (перепутат порядок соединения внутри фолда) ещё вообще то нужно дойти. Т..е я имею ввиду до этоо момента можно сделать миллион ошибок от которых защищает система типов (вот как ТС), а перепутать то что перепутывается в хаскеле ни в одном другом языке (ну кроме агды/идриса/кока и т.п) ничего помешать не может. Странно что ты это записываешь себе в аргументы.

AndreyKl ★★★★★ ()
Последнее исправление: AndreyKl (всего исправлений: 1)
Ответ на: комментарий от Crocodoom

А вы пока напишите, какой смысл Вы вкладываете в ремарку к toList «List of elements of a structure, from left to right.».

С учётом того, что toList определён на Foldable, то очевидно, что left to right относится к свёртке слева и свёртке справа. То есть toList должен вернуть элементы в том порядке, в котором их использует свёртка слева. Порядок определяется структурой. Например для Data.Set.

> import qualified Data.Set as S
> import Data.Foldable
> toList $ S.fromList [1,3,2,5,5,0]
[0,1,2,3,5]
monk ★★★★★ ()
Ответ на: комментарий от AndreyKl

так же об этом есть упоминание на стр. 202 той же книги (evaluating of foldr... performed from right-to-left)

С этим я и не спорю. foldr и foldl определяются в предположении, что элементы в структуре имеют какой-то порядок. Причём горизонтальный (лево и право).

Но даже для списка никто не утверждает, что голова списка обязана находиться слева. Может быть справа. Например, если разработчик араб.

Правда, такого (про конструкторы) я не встечал объяснения как дал крокодум.

Вот с этим спорю. Поэтому и Queue как пример. Или даже toList (Left 5), который возвращает пустой список.

Я бы сказал надо начинать с самого последнего дерева в списке, взяв самое последнее дерево в его списке (если существует) и т.д...

С деревьями в списке понятно. А вот элемент в голове: он правее или левее деревьев в списке? А правое дерево целиком правее левого дерева или надо брать первый ряд правого, первый ряд левого, второй ряд правого, второй ряд левого и т.д.?

Что до аргумента «делают меньше ошибок на хаскеле» - так до этого (перепутат порядок соединения внутри фолда) ещё вообще то нужно дойти.

В этом и проблема. Там где в языке система типов слабее или частично проверяет во время выполнения, разработчик начинает с тестов. В чистых языках тесты писать одно удовольствие. Но в Хаскеле разработчик потратив кучу времени, чтобы побороть компилятор, на тесты часто забивает: «типизацию проходит, скорее всего правильно, дальше думать лень».

А потом получаем ошибки типа:

(leksah:19935): Gtk-CRITICAL **: gtk_text_view_scroll_mark_onscreen: assertion 'get_buffer (text_view) == gtk_text_mark_get_buffer (mark)' failed

.

Причём ошибка висит уже полгода. Или вот такая феерия: https://github.com/leksah/leksah/issues/137.

А когда ошибка уже всплыла, то быстро её побороть в Хаскеле мешает ленивость языка. Функция падает не там, где произошла ошибка, а там, где кто-то попытается прочитать результат. И в случае чистых функций непонятно, как сделать гарантии на данные между модулями. Например, пишу я функцию для перевода градусов Цельсия в Фаренгейты:

ctof x = if x < 273.15 then error "Bad tempeture" else x*9/5+32

Потом в другом модуле кто-то использует с неверными данными l2 = map ctof l1. Потом кто-то третий попытается прочитать значение из l2 (которое к тому моменту в совсем другой переменной) и в этот момент получит ошибку. Но чтобы выяснить, откуда ошибка, надо проследить всю историю данных. А если где-то встречается код типа ddd = if cond then l2 else anotherData, то её не проследить без вывода всех промежуточных значения (в ленивом языке, да). К счастью, есть лазейка trace, но всё равно крайне неудобно.

monk ★★★★★ ()
Ответ на: комментарий от monk
λ> let x = push 3 $ push 2 emptyQ 
λ> x == Queue [] (3 : 2 : [])
True
λ> toList x
[3,2]
λ> let y = snd. pop $ push 3 $ push 2 $ push 1 emptyQ
λ> y == Queue (2 : 3 : []) []
True
λ> toList y
[2,3]

Не совсем понимаю, что вы хотели показать своим примером...

Queue [] (3 : 2 : []) трансформируется в [3,2], а Queue (2 : 3 : []) [] в [2,3].

В полном соответствии с тем, как должен работать toList t, если следовать моему принципу (который вы пытаетесь оспорить)

Дерево конструкторов любого данных можно записать в строчку (и именно так мы и задаем их в хаскеле), и эту строчку можно прочитать слева направо .. toList должен выдавать в точности такой же порядок элементов

Crocodoom ★★ ()
Последнее исправление: Crocodoom (всего исправлений: 1)
Ответ на: комментарий от Crocodoom

Не совсем понимаю, что вы хотели показать своим примером...

То что для очереди «добавить 2, добавить 3» и «добавить 1, добавить 2, добавить 3, забрать элемент» является одним и тем же состоянием: очередь с элементами 2 и 3 (именно в этом порядке).

Но Ваша версия toList для «добавить 2, добавить 3» возвращает элементы очереди в обратном порядке.

monk ★★★★★ ()
Ответ на: комментарий от monk

Там где в языке система типов слабее или частично проверяет во время выполнения, разработчик начинает с тестов. В чистых языках тесты писать одно удовольствие. Но в Хаскеле разработчик потратив кучу времени, чтобы побороть компилятор, на тесты часто забивает: «типизацию проходит, скорее всего правильно, дальше думать лень».
А потом получаем ошибки типа https://github.com/leksah/leksah/issues/455

Цитируйте в следующий раз полностью, а не выдирайте из контекста. Вы прилично так исказили смысл моих слов.

Я написал:

Типизацию проходит, скорее всего правильно, дальше думать лень. Проверь сам.

То есть я предоставил фикс кода ТС, который проходит типизацию, но может потенциально содержать семантические ошибки, и предложил ему самому проверить, что код работает правильно — то есть как раз провести эти самые тесты. А вовсе не говорил «отправляй этот код в продакшен, 100% рабочий». Впрочем, в последствии у меня появилось больше времени, и я всё же проверил его сам, и даже подробно расписал, как он был получен.

Crocodoom ★★ ()
Ответ на: комментарий от monk

Я никогда не утверждал, что toList обязан следовать какой-то семантике, которую лично Вы вкладываете в свою структуру данных. Я говорил, что он должен сохранять порядок значений из строчной записи дерева конструкторов — и он его сохраняет в Queue.

А если вам нужен какой-то свой, особый toList', который следует вашей семантике — так напишите его. Но при чём тут будет Foldable?

Crocodoom ★★ ()
Последнее исправление: Crocodoom (всего исправлений: 2)
Ответ на: комментарий от Crocodoom

Цитируйте в следующий раз полностью, а не выдирайте из контекста. Вы прилично так исказили смысл моих слов.

Так критика относилась не к Вам, а именно к процитированному утверждению. Я его уже много раз видел в разных вариациях. Ваше — наиболее лаконичное. И ошибки в leksah свидетельствуют, что некоторые его принимают на вооружение именно в процитированной версии без дополнительных ограничений.

monk ★★★★★ ()
Ответ на: комментарий от Crocodoom

он должен сохранять порядок значений из строчной записи дерева конструкторов

Не должен. Он должен сохранять порядок элементов обходимой структуры данных. Для очереди это порядок элементов в очереди.

Так же как Data.Traversable.

monk ★★★★★ ()
Ответ на: комментарий от Crocodoom

что он должен сохранять порядок значений из строчной записи дерева конструкторов

А если структура данных имеет внутри индекс, то его тоже надо вытаскивать в список? Например

data OrderedKeyValue a b = OrderedKeyValue { data::[(a,b)], index :: Map a b}

newOrdered :: [(a,b)] -> OrderedKeyValue a b
newOrdered x = OrderedKeyValue x (makeIndex x)

С моей точки зрения toList (OrderedKeyValue data index) = data

monk ★★★★★ ()
Ответ на: комментарий от monk

Ок, теперь я понял вашу мысль. Тот Foldable, которого я придерживался — он естественен с точки зрения именно структуры самого типа, и он является дефолтным, в т.ч. его дает deriving Foldable. Но возможны и другие инстансы, отвечающие какой-то дополнительной семантике, которой оснащается тип, а deriving Foldable эту семантику может портить. Спасибо за хороший пример с очередью :)

Crocodoom ★★ ()
Ответ на: комментарий от monk

Ваш пример проходит компиляцию, однако не «заменяет n-арные конструкторы данных на n-арные функции», а именно этим должен заниматься foldr.

Где написано, что он должен делать именно это?

Это определение катаморфизма. Там как раз речь идёт о замене конструкторов на подходящие по типам и арности функции. Все разумные инстансы Foldable должны работать как катаморфизмы. Вот откуда я это и взял, кажется. AndreyKl это вам тоже.

https://traditio.wiki/Катаморфизм

Катаморфизм в функциональном программировании

В функциональном программировании катаморфизм является обобщением свёртки (для списков) на произвольные алгебраические типы данных, что может быть описано при помощи начальных алгебр (понятие из теории категорий). ... Как известно, алгебраический тип данных является размеченным объединением декартовых произведений различных типов, в том числе и сам такой тип может включаться в своё определение рекурсивно. Каждому декартову произведению в языке Haskell соответствует один конструктор данных, после которого перечисляется 0 или более полей некоторых типов.

Однако я пока затрудняюсь показать или опровергнуть, что свёртка дерева «в ширину» (а не «в глубину») тоже является катаморфизмом. Вполне возможно, что является. И также не могу сказать, является ли катаморфизмом свёртка Queue в том виде, в котором её хочет monk.

Crocodoom ★★ ()
Последнее исправление: Crocodoom (всего исправлений: 1)
Ответ на: комментарий от Crocodoom

Так deriving в принципе является некоторой формулировкой по-умолчанию. Но на практике в любой структуре со служебными данными (индексы, итоги, кэш, ...) надо реализовывать вручную не только Foldable, но и Show.

Про deriving Foldable полностью согласен. У него нет никакой информации кроме порядка и типа полей, а значит порядок элементов определяется порядком полей в структуре.

monk ★★★★★ ()
Ответ на: комментарий от Crocodoom

я пока затрудняюсь показать или опровергнуть, что свёртка дерева «в ширину» (а не «в глубину») тоже является катаморфизмом

законы проверь. раз это функтор, то должно быть

foldMap f . fmap g = foldMap (f . g)

anonymous ()
Ответ на: комментарий от Crocodoom

Это определение катаморфизма. Там как раз речь идёт о замене конструкторов на подходящие по типам и арности функции.

Так в моём примере foldr f acc (RoseTree x ts) = foldr (flip (foldr f)) (f x acc) ts тоже RoseTree x ts заменяется на foldr (flip (foldr f)) (f x acc) ts, который подходит по типам и арности.

Нигде не указывается, что функция в катаморфизме обязана сохранять порядок аргументов.

monk ★★★★★ ()
Ответ на: комментарий от Crocodoom

monk

Однако я пока затрудняюсь показать или опровергнуть, что свёртка дерева «в ширину» (а не «в глубину») тоже является катаморфизмом. Вполне возможно, что является.

Теперь разобрался. Свёртка дерева «в ширину» катаморфизмом не является, и посему может называться свёрткой лишь условно. Буду использовать просто слово «обход». Дело в том, что инстанс foldMap для обхода «в ширину» невозможно написать естественной рекурсией по Tree a, из списка моноидов поддеревьев мы не можем слепить моноид дерева, происходит потеря информции. То есть, имея дерево Tree a = Tree a [Tree a], и уже обойдя в ширину каждое дерево Tree a в лесе, мы не сможем скомбинировать обход в ширину исходного дерева.

И также не могу сказать, является ли катаморфизмом свёртка Queue в том виде, в котором её хочет monk.

А вот свёртка для обхода очереди как outbox .. reverse inbox (семантический порядок элементов для Queue) катаморфизмом является, так что тут было всё нормально.

Crocodoom ★★ ()
Последнее исправление: Crocodoom (всего исправлений: 1)
Ответ на: комментарий от Crocodoom

Дело в том, что инстанс foldMap для обхода «в ширину» невозможно написать естественной рекурсией по Tree a, из списка моноидов поддеревьев мы не можем слепить моноид дерева, происходит потеря информции.

А где такое требование? По определению катаморфизма единственное требование: cata f = h, h . in = f . Fh.

То есть катаморфизмом является любая конструкция вида

instance Foldable RoseTree where
    foldr _ acc RoseEmpty       = acc
    foldr f acc (RoseTree x []) = f1 f x acc
    foldr f acc (RoseTree x ts) = g1 f acc x ts
при условии корректных типов f1 и g1.

В частности

instance Foldable RoseTree where
   foldr _ acc RoseEmpty       = acc
   foldr f acc (RoseTree x []) = f x acc
   foldr f acc (RoseTree x ts) = foldr f acc $ x:(getBF ts)

getBF :: [RoseTree a] -> [a]
getBF x = getFrom 0 x

getFrom :: Int -> [RoseTree a] -> [a]
getFrom n x = case concat $ map (getLevel n) x of
                [] -> []
                y -> y ++ getFrom (n+1) x

getLevel :: Int -> RoseTree a -> [a]
getLevel 0 (RoseTree x xs) = [x]
getLevel n (RoseTree x xs) = concat $ map (getLevel (n-1)) xs

подходит под все требования катаморфизма.

monk ★★★★★ ()
Ответ на: комментарий от monk

Дело в том, что инстанс foldMap для обхода «в ширину» невозможно написать естественной рекурсией по Tree a, из списка моноидов поддеревьев мы не можем слепить моноид дерева, происходит потеря информции.

А где такое требование?

Это напрямую следует из определения катаморфизма для рекурсивных типов данных. Мы определяем data TreeF a r = Tree a [r], и type Tree a = Fix (TreeF a). После чего катаморфизм cata :: Functor f => (f r -> r) -> Fix f -> r (см. Data.Fix), где f = TreeF a, f r -> r = TreeF a r -> r — некая алгебра над TreeF a, и Fix f = Fix (Tree F a) = Tree a — само дерево.
Подробнее: Understanding F-Algebras

Если немного упростить определение катаморфизма, вычистив из него весь теоркат и выкинув Fix, то получится как раз то, о чём я говорю: катаморфизм рекурсивного типа данных — это рекурсивная замена конструкторов на произвольные функции подходящей арности и типов.
Подробнее: Катаморфизм — Традиция

По определению катаморфизма единственное требование: cata f = h, h . in = f . Fh. То есть катаморфизмом является любая конструкция вида

instance Foldable RoseTree where
    foldr _ acc RoseEmpty       = acc
    foldr f acc (RoseTree x []) = f1 f x acc
    foldr f acc (RoseTree x ts) = g1 f acc x ts

А у вас рекурсивной замены констукторов нет, так что не катит. Ну или раскройте своё «то есть», как вы из абстрактного h . in = f . Fh выписали instance Foldable RoseTree. Почему именно так, а не иначе. Почему у вас три паттерн-матчинга, а не два (по числу конструкторов). Кстати, конструктор RoseEmpty можно выкинуть из data RoseTree a: для Rose Tree он не нужен.

Crocodoom ★★ ()
Ответ на: комментарий от monk

Кстати, эти getFrom и getLevel можно сократить, если вспомнить про замечательную функцию unfoldr для списков. Я через неё и сделал обход в ширину для дерева. А потом долго думал, является ли такой обход катаморфизмом, и пришёл к выводу, что нет, не является.

AndreyKl, monk
В общем написал небольшую демонстрацию того, что такое катаморфизм (обобщенная свёртка) на примере Rose Tree. Используется пакет Data.Fix и функция cata из него. Для понимания этого хозяйства достаточно прочитать статью Understanding F-Algebras, знание теорката не требуется.

import Data.List
import Data.Foldable
import Control.Arrow
import Data.Fix
import qualified Data.Tree as DT -- Only for drawing a Tree

-- Tree definition via Fix
data TreeF a r = Tree a [r] deriving (Eq, Show)

type Tree a = Fix (TreeF a)

-- Making a Tree
tree :: a -> [Tree a] -> Tree a
tree a ts = Fix $ Tree a ts 

t = tree 1 [tree 2 [tree 3  [tree 4  [], tree 5  []],
                    tree 6  [tree 7  [], tree 8  []]],
            tree 9 [tree 10 [tree 11 [], tree 12 []],
                    tree 13 [tree 14 [], tree 15 []]]]

-- For using of 'cata'
instance Functor (TreeF a) where
    fmap f (Tree a rs) = Tree a (map f rs)

-- treeSum t == 120
treeSum = cata algebra where
    algebra :: Num a => TreeF a a -> a
    algebra (Tree a rs) = a + sum rs

-- treeDepth t == 4
treeDepth = cata algebra where
    algebra :: (Num r, Ord r) => TreeF a r -> r
    algebra (Tree a rs) = 1 + foldr max 0 rs

-- Drawing a Tree
drawTree t = DT.drawTree $ show <$> cata algebra t where
    algebra :: TreeF a (DT.Tree a) -> DT.Tree a 
    algebra (Tree a rs) = DT.Node a rs

-- Two newtypes for two Foldable Tree instances
newtype DepthTree a   = Depth {getDepth :: Tree a}
newtype BreadthTree a = Breadth {getBreadth :: Tree a}

-- toList (Depth t) == [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
instance Foldable DepthTree where
    foldMap f (Depth t) = cata (algebra f) t where
        algebra :: Monoid r => (a -> r) -> TreeF a r -> r
        algebra f (Tree a rs) = f a `mappend` mconcat rs

-- toList (Breadth t) == [1,2,9,3,6,10,13,4,5,7,8,11,12,14,15]
instance Foldable BreadthTree where -- Can't be done via cata!
    foldMap f (Breadth (Fix (Tree a ts))) =
        f a `mappend` mconcat (unfoldr next ts) where
            next [] = Nothing
            next ts = Just $ first mconcat $ second concat $ unzip $
                             (\(Fix (Tree a ts)) -> (f a, ts)) <$> ts

Как можно видеть, все функции (treeSum, treeDepth, drawTree) и инстанс Foldable для обхода в глубину реализованы через cata algebra. А вот инстанс Foldable для обхода в ширину реализовать через cata algebra никак не получается, потому что

Дело в том, что инстанс foldMap для обхода «в ширину» невозможно написать естественной рекурсией по Tree a, из списка моноидов поддеревьев мы не можем слепить моноид дерева, происходит потеря информции. То есть, имея дерево Tree a = Tree a [Tree a], и уже обойдя в ширину каждое дерево Tree a в лесе, мы не сможем скомбинировать обход в ширину исходного дерева.

Всё это, конечно, можно переписать и без привлечения Data.Fix и cata, а напрямую определив data Tree a = Tree a [Tree a]. После чего параметризуем все алгебры над типом соответствующим кортежем, и выписываем рекурсивную свёртку по произвольной алгебре. Как это делать, описано здесь: Катаморфизм — Традиция.

Crocodoom ★★ ()
Ответ на: комментарий от Crocodoom

Подробнее: Катаморфизм — Традиция

Так там же указано:

Наконец, необходимо отметить, что приведённые примеры катаморфизмов для различных типов данных, а также общий способ построения катаморфизма для произвольного алгебраического типа данных — всё это лишь частная реализация теоретического механизма. Теория не ограничивает способы создания катаморфизмов, она лишь определяет, что такое катаморфизм и как его можно использовать на практике. Использование синонима типа и функций типа foldT — это один из многих способов имплементации теоретического понятия в коде функционального языка. То, каким способом определить катаморфизм для своего типа данных, разработчик программного обеспечения выбирает самостоятельно.

То есть, если функция Дирихле является всюду разрывной, то это не значит, что все всюду разрывные функции должны строиться как произведение функции Дирихле на какую-либо функцию.

по определению для катаморфизма требуется соответствие типа (на входе дерево, на выходе значение) и чтобы он являлся гомоморфизмом. Я так понимаю, для Хаскела гомоморфизм это

foldMap f . fmap g = foldMap (f . g)

Оба условия для свёртки в ширину выполняются.

monk ★★★★★ ()
Ответ на: комментарий от monk

Вашу мысль я понял. Вы утверждаете, что если ваш катаморфизм нельзя задать, как задаю его я (через параметризованные алгебры, или более общо через cata из Data.Fix), то это не значит, что это не катаморфизм. Вы опираетесь только базовое определение в терминах теорката.

А где такое требование? По определению катаморфизма единственное требование: cata f = h, h . in = f . Fh.

по определению для катаморфизма требуется соответствие типа (на входе дерево, на выходе значение) и чтобы он являлся гомоморфизмом.

Хорошо, давайте тогда наконец нормально разберём это ваше определение (из Википедии):

Consider an initial F-algebra (A, in) for some endofunctor F of some category into itself. Here in is a morphism from FA to A. Since it is initial, we know that whenever (X, f) is another F-algebra, i.e. a morphism f from FX to X, there is a unique homomorphism h from (A, in) to (X, f). By the definition of the category of F-algebras, this h corresponds to a morphism from A to X, conventionally also denoted h, such that h . in = f . Fh. In the context of F-algebras, the uniquely specified morphism from the initial object is denoted by cata f and hence characterized by the following relationship:
h = cata f
h . in = f . Fh

Я начну первый, для свёртки в глубину:

  1. category --> Hask
  2. endofunctor F --> TreeF a
  3. initial F-algebra (A, in) --> (Fix (TreeF a), algebra_init)
    algebra_init :: TreeF a (Fix (TreeF a)) -> Fix (TreeF a)                    
    algebra_init (Tree a rs) = Fix $ Tree a rs
    
  4. arbitrary F-algebra (X, f) --> (Monoid r => r, algebra_fold f)
    algebra_fold :: Monoid r => (a -> r) -> TreeF a r -> r                      
    algebra_fold f (Tree a rs) = f a `mappend` mconcat rs
    
  5. unique homomorphism h --> cata (algebra_fold f)

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

  1. Категория понятна - это в любом случае Hask
  2. Какой у вас эндофунктор F рассматривается?
  3. Какая у него начальная F-алгебра?
  4. Какую F-алгебру вы задаете для свёртки в ширину?
  5. Каким именно катаморфизмом вы делаете свёртку?
Crocodoom ★★ ()
Ответ на: комментарий от Crocodoom

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

Первые три пункта те же.

initial F-algebra (A, in) --> (Tree a, algebra_init)

4. arbitrary F-algebra (X, f) --> (Monoid r => r, f)

5. unique homomorphism Tree a -> r

h :: Tree a -> r
h = foldMap f

Реализация foldMap пусть будет твоя:

foldMap :: Monoid r => (a -> r) -> Tree a -> r
foldMap f (Fix (Tree a ts)) =
        f a `mappend` mconcat (unfoldr next ts) where
            next [] = Nothing
            next ts = Just $ first mconcat $ second concat $ unzip $
                             (\(Fix (Tree a ts)) -> (f a, ts)) <$> ts

monk ★★★★★ ()
Ответ на: комментарий от monk

Первые три пункта те же.

4. arbitrary F-algebra (X, f) --> (Monoid r => r, f)

Что такое ваша f в правой части -->? Если вы имеете в виду ту f :: (a -> r), которая позже передаётся в foldMap, то она не подходит по типам. F-Algebra должна действовать FX -> X, то есть TreeF a r -> r для этого случая, раз «первые три пункта те же».
Если вы не стали уточнять f, а оставили её «произвольной», как в левой части -->, то так не пойдет, потому что без неё не задана алгебра, а значит говорить о катаморфизме пока бессмысленно.

Crocodoom ★★ ()
Ответ на: комментарий от Crocodoom

F-Algebra должна действовать FX -> X, то есть TreeF a r -> r для этого случая

Мда. Дошло. Без рекурсии и Fix нельзя получить начальную алгебру. А с ними целевая алгебра с типом TreeF a r -> r не может получить доступ к структуре поддеревьев.

monk ★★★★★ ()