Слишком много аргументов в обобщенной версии функции fold для BST

Запуск fold (+) 0 sample выдает ошибку о том, что (+) применяется к слишком большому количеству аргументов. Почему?

data(Ord a, Show a, Read  a) => BST a = Void | Node {
    val :: a,
    left, right :: BST a
} deriving (Eq,  Ord,  Read,  Show)

sample = Node 5 (Node 3 Void Void) (Node 10 Void Void)

fold :: (Read a, Show a, Ord a) => (a -> b -> b ->  b) -> b -> BST a -> b
fold _ z Void         = z
fold f z (Node x l r) = f x (fold f z l) (fold f z r)

Occurs check: cannot construct the infinite type: a = a -> a
Probable cause: `+' is applied to too many arguments
In the first argument of `fold'', namely `(+)'
In the expression: fold' (+) 0 sample

См. также: свернуть


fold haskell binary-search-tree
person gremo    schedule 04.02.2011    source источник
comment
Вы можете попробовать сделать свой тип экземпляром Foldable и Проходимый   -  person Dan Burton    schedule 04.02.2011

Ответы (2)


arrow_upward
1
arrow_downward

Вашему fold требуется функция типа a -> b -> b -> b в качестве первого параметра, то есть функция, которая принимает три аргумента. (+), с другой стороны, принимает только два аргумента.

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

person sth    schedule 04.02.2011
comment
хорошо, fold (\x y z -> x+y+z) 0 sample работает и суммирует все элементы BST. Однако, несмотря на то, что foldr и foldl, определенные в Haskell, довольно просты для понимания, я не могу представить, как функция BST fold на самом деле применяется к элементам дерева. Я имею в виду порядок, как ссылка на вики Haskell в первом посте. - person gremo; 04.02.2011
comment
Гремо, когда вы сворачиваете дерево, у вас есть три части информации: значение, которое вы получили, свернув левое поддерево, значение, которое вы получили, свернув правое поддерево, и значение, которое находится в этом конкретном узле. Это отличается от списка, потому что списки не разветвляются, как деревья, поэтому они просто имеют текущее значение и вычисленное значение из остальной части списка. Подпись типа сгиба зависит от типа, который вы складываете. - person Chris Smith; 04.02.2011
comment
Спасибо, очень полезное объяснение. - person gremo; 04.02.2011

arrow_upward
1
arrow_downward

Ваша проблема в том, что вы применяете функцию к 3 аргументам. Первый параметр в сигнатуре типа говорит сам за себя.

fold :: (a -> b -> b -> b) -> b -> BST a -> b
fold f z (Node x l r) = f x (fold f z l) (fold f z r)

(+) принимает только 2 аргумента, но когда вы передаете его, он пытается оценить это:

(+) x (fold (+) z l) (fold (+) z r) -- 3 arguments! =P

Вероятно, вы захотите сбросить бинарную функцию (a -> a -> a). Предположим, вы хотите использовать (+). Вы хотите, чтобы результат был таким:

fold f z (Node x l r) = x + (fold f z l) + (fold f z r)

Отсюда легко обобщить: просто замените + на f с инфиксом.

fold f z (Node x l r) :: (a -> a -> a) -> a -> BST a -> a
fold f z (Node x l r) = x `f` (fold f z l) `f` (fold f z r)
person Dan Burton    schedule 04.02.2011