Реализация катаморфизма для не двоичных деревьев в сравнении с шаблоном композитного дизайна

Question

На данный момент мечта все еще продолжается, на каждой концепции Haskell, которую я узнаю, я более соблазнен. И все же я не полностью выполнил работу над этим драгоценным ответом @Луки на Мой предыдущий вопрос о катаморфизме, и я вернусь к нему, пока все в порядке. Речь шла об этом примере кода в Википедии, имея дело с Катаморфизм на бинарных деревьях.

Тем не менее, я попытался реализовать катаморфизм Не бинарный Деревья, но я сталкиваюсь с некоторыми проблемами:

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                                 , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y] 

- Эта последняя строка не будет, пожалуйста, GHC на "Map G [y]

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

maxInList :: [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = (+) } 

- и этот самый яркий сумтри тоже неправ для GHC

Я вижу> и +, как операторы C ++> и +. Так что я не понимаю, что GHC злится на меня, не давая ему objets, реализуя Opertor>/+ или нет.

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

Как бы вы исправить этот код?

И последний вопрос, я также пытаюсь сделать это, потому что составной шаблон оказался наиболее важным для меня в C ++. И, очевидно, я вижу, что его можно было почти описано только в одной/двух строке в Хаскелле (это действительно удивительно для меня).

Но как бы вы могли выразить тот факт, что листья и составной конструктор композиции могут иметь какой -то тот же интерфейс? (Я знаю, что это не хорошее слово, так как данные не являются изменчивыми, но я надеюсь, что вы сможете догадаться-понять мою заботу/цель)

Это общая ошибка компиляции;

src\Main.hs:27:79:
    Couldn't match expected type `[r]'
           against inferred type `Composition a'
    In the expression: y
    In the second argument of `map', namely `[y]'
    In the expression: map g [y]

src\Main.hs:30:20:
    Could not deduce (Ord a) from the context ()
      arising from a use of `>' at src\Main.hs:30:20-24
    Possible fix:
      add (Ord a) to the context of the type signature for `maxOfPair'
    In the expression: (x > y)
    In the expression: if (x > y) then (x) else (y)
    In the definition of `maxOfPair':
        maxOfPair x y = if (x > y) then (x) else (y)

src\Main.hs:41:0:
    Occurs check: cannot construct the infinite type: a = [a] -> [a]
    When generalising the type(s) for `sumTree'

РЕДАКТИРОВАТЬТак что это окончательная версия для не бинарного катаморфизма

data Composant a = Leaf a
                 | Composite [Composant a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                             , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composant a →  r
foldComposition a@(CompositionAlgebra {leaf = f}) (Leaf x) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) =  g(map(foldComposition a) ys)

maxOfPair :: Ord a ⇒ a →  a →  a
maxOfPair x y = if( x > y) 
                then (x) 
                else (y)

maxInList :: Ord a => [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

addList :: Num a ⇒ [a] → a
addList (x:xs) = x + addList xs 

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = addList } 

И в соответствии с действительным ответом ниже: то, что я просил, эквивалентен Haskell, эквивалентным контрактам интерфейсов C ++, представляется ограничениями Typeclasses.

Таким образом, композит схемы проектирования будет достигнут путем применения ограничений тип -классов при построении композиции a. Может быть, новые специализированные данные должны быть определены. Но я должен выучить typeclasses, прежде чем делать это :-)

Answer 1

Здесь есть несколько разных ошибок, поэтому я не уверен, что лучший способ справиться с этим, но, черт возьми.

В будущем попытайтесь включить больше ошибок, которые предоставляет GHC.

В:

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y]

Функция foldCompose Имеет две ошибки, которые я вижу, только одна из которых будет пойман в шарике.

1. Вы совпадаете с шаблонами на (Composite [y]), который будет соответствовать спискам одного элемента. Вы, вероятно, хотите (Composite ys), который связывает ys ко всему списку.

2. map g [y] не пройдет проверку типа, потому что вы уже определили g как соблюдает список r, но вы даете ему список a.

   Чтобы преобразовать a чтобы r вам нужно применить свой CompositionAlgebra к этому: g (map (foldComposition a) ys)

Так что я бы написал это как:

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) = g (map (foldComposition a) ys)

Для вашей следующей ошибки:

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

В Haskell переменная типа (например a Здесь) все его одиноким может быть заполнено любым типом со стороны вызывающего абонента по выбору абонента.

Это означает, что в вашем типе подпись вы утверждаете, что функция maxPair будет работать на каждый тип ввода. GHC жалуется (по -своему), что оператор > не работает для каждый Тип и, следовательно, отказывается компилировать вашу программу.

Вам нужно использовать Typeclasses Для решения этой проблемы. В Haskell Typeclasses позволяют вызывающему вызывающему вызов для использования, но с некоторыми ограничениями. Я рекомендую прочитать Haskell Учебное пособие по Typeclasses.

Подпись правильного типа будет:

maxOfPair :: Ord a => a →  a →  a

Который применяет Ord ограничение типа a.

Кроме того, вы должны использовать стандартную функцию max.

Answer 2

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

Поместить Элем функция, которая проверяет, если список содержит определенное значение. Вы можете определить это как

elem _ [] = False
elem x (y:ys) | x == y = True
              | otherwise = elem x ys

Какая подпись имеет эту функцию? Похоже elem :: a -> [a] -> Bool. Анкет Но компилятор будет жаловаться, потому что вы написали x == y, и не для каждого a а == функция определяется только для тех a которые в Класс эквалайза. Анкет Таким образом, вам нужно указать что -то вроде «для всех, кто находится в уравнении ...». И именно для этого вам нужно =>. Анкет Так что правильная подпись для elem является elem :: Eq a => a -> [a] -> Bool.

А @ дает вам возможность дать целую структуру имя и одновременно соответствовать ей шаблона. Например, если у вас есть шаблон a@(x:xs) и вы называете эту функцию с [1,2,3,4], тогда a является [1,2,3,4], xявляется 1 а также xs является [2,3,4].