Проблема с пониманием treeort в Haskell

Question

Я пытаюсь выяснить, как работает дерево с here (я понимаю, сгладить, вставить и свернуть).

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

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

Answer 1

что делается в Treesort применяет вставку для каждого элемента в списке, создавая таким образом дерево и затем сглаживая его.

Точно верно.

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

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

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

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

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

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

a = \e -> (f) e 

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

a e = (f) e 

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

treesort = flatten . foldr insert Leaf 

такая же, как

treesort list = (flatten . foldr insert Leaf) list