Проблема понимания деревьев в Haskell

Question

Я пытаюсь выяснить, как именно работает сортировка деревьев из здесь (я понимаю, что flatten, insert и foldr).

Я полагаю, что в TreeSort происходит применение вставки для каждого элемента в списке , в результате чего создается дерево, а затем выравнивается дерево. Единственная проблема, которую я не могу преодолеть, это то, где скрывается список (то есть аргумент функции) (потому что он нигде не записывается как аргумент, кроме объявления типа функции).

Еще одна вещь: поскольку оператор точки является составлением функции, почему я меняю ошибку: treesort = flatten . foldr insert Leaf на treesort = flatten( foldr insert Leaf )?

Answer 1

Что происходит при сортировке деревьев, так это применение вставки для каждого элемента в списке, создавая дерево и затем выравнивая его.

Точно верно.

[Где скрывается список?]

На функциональном языке вам не нужно указывать аргументы значения типа функции. Например, если я напишу

f = concat . map (map toUpper) 

Я получаю функцию типа [[Char]] -> [Char]. это Функция ожидает аргумент, даже если в определяющем уравнении нет аргумента. Это точно так же, как если бы я написал

f strings = (concat . map (map toUpper)) strings

Так как оператор точки является композицией функций, почему неправильно менять f . g на f (g)?

Они не имеют в виду одно и то же. Что происходит, когда каждый применяется к x?

(f . g) x  = f (g x)

(f (g)) x  = (f g) x

Вы можете видеть, что приложения ассоциируются по-разному, и f. g отличается от f g.

Это ошибка типа, потому что foldr insert Leaf - это функция от списков к деревьям, а flatten предназначена для применения к одному дереву, а не к функции.

Answer 2

Чтобы ответить на ваш последний вопрос первым, вы получаете сообщение об ошибке, потому что . является оператором композиции функций, который принимает две функции (в данном случае flatten и foldr insert Leaf). Если вы хотите переписать код без использования ., вам нужно создать функцию, которая принимает некоторый параметр:

-- // Pass the 'list' to the first function and the 
-- // result of the call to the second function
treesort list = flatten (foldr insert Leaf list)

Это также объясняет, где скрывался параметр list. При составлении функций вам не нужно явно записывать параметры, потому что результатом выражения f . g является функция, которая принимает некоторый параметр, вызывает g, а затем вызывает f:

-- // function composition..
composed = f . g
-- // ..is equivalent to declaring a function:
composed x = f (g x)

Answer 3

Иногда, если вы не знакомы с бессмысленным стилем, полезно сделать эпсилон-преобразование мысленно.

Если f является выражением с типом функции, то его можно преобразовать в \ е -> (е) е

И, если у нас есть определение типа

a = \e -> (f) e

мы всегда можем смело переписать его как

a e = (f) e

Таким образом

treesort = flatten . foldr insert Leaf 

совпадает с

treesort list = (flatten . foldr insert Leaf) list