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

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

0 голосов
/ 22 сентября 2018

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

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 в этом случае, мне не ясно с этим.Спасибо!

Ответы [ 2 ]

0 голосов
/ 22 сентября 2018

Есть два различия между 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
0 голосов
/ 22 сентября 2018

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

foldl :: (<b>b -> a -> b</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 <b>(flip</b> treeInsert<b>)</b> 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 = <b>foldr</b> treeInsert EmptyTree nums

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

insertTree 8 (insertTree 6 (insertTree 4 EmptyTree))

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

...