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

Question

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

Тем не менее, я попытался реализовать катаморфизм для недвоичных деревьев, но у меня возникли некоторые проблемы:

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 на "карте 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 злится на меня, если я не предоставлю ему объект, реализующий opertor >/+ или нет.

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

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

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

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

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

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++ Interfaces, похоже, является ограничениями классов типов.

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

Answer 1

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

В будущем постарайтесь включить больше ошибок, которые выдает 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 жалуется (по-своему), что оператор > не работает для всех типов, и поэтому отказывается компилировать вашу программу.

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

Правильная сигнатура типа:

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

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

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

Answer 2

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

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

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

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