Не может создать бесконечный тип при использовании foldl

Question

Я определил двоичное дерево и использовал свои функции для создания нового дерева.

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
    | x < a     = Node a (treeInsert x left) right
    | x > a     = Node a left (treeInsert x right)
    | otherwise = Node a left right

когда я выполнил это в терминале:

let nums = [8,6,4,1,7,3,5]
let numsTree= foldl treeInsert EmptyTree nums

Он вернул ошибку.

Occurs check: cannot construct the infinite type: a ~ Tree a
Expected type: Tree a -> Tree a -> Tree a
Actual type: a -> Tree a -> Tree a

однако после того, как я изменил foldl на foldr, все работает.

let numsTree= foldr treeInsert EmptyTree nums

Кто-нибудь может сказать мне, почему? И в чем разница между foldl и foldr в этом случае, мне не ясно с этим. Спасибо!

Answer 1

Есть два различия между foldr а также foldl, Важным является способ, которым они заключают в скобки свои вычисления:

foldl (+) 0 [1..3] = ((0 + 1) + 2) + 3
foldr (+) 0 [1..3] = 1 + (2 + (3 + 0))

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

> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

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

Итак, в вашем случае, два варианта:

foldr treeInsert EmptyTree nums
foldl (flip treeInsert) EmptyTree nums

Answer 2

Подпись foldl является:

foldl :: (b -> a -> b) -> b -> [a] -> b

Мы применяем foldl с функцией (insertTree) также как и Tree и список Int s, так что это означает, что b ~ Tree Int, а также a ~ Int,

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

Мы можем решить это с помощью flip :: (a -> b -> c) -> b -> a -> c:

let numsTree = foldl (flip treeInsert) EmptyTree nums

flip переворачивает параметры, так f x y == flip f y x,

foldl означает, что для списка [8,6,4], мы будем применять это как:

insertTree 4 (insertTree 6 (insertTree 8 EmptyTree))

Мы также можем решить использовать foldr :: (b -> a -> b) -> b -> [a] -> b(обратите внимание, что порядок параметров изменился) как:

let numsTree = foldr treeInsert EmptyTree nums

тогда для списка [8,6,4] это приведет к:

insertTree 8 (insertTree 6 (insertTree 4 EmptyTree))

Поскольку порядок, в котором элементы вставляются в Tree может иметь влияние, оба семантически, а не эквивалентны.