Как мне реализовать эту функцию сгиба?

Если мы посмотрим на сигнатуру функции:

fold_plant :: (x -> x -> x) -> (Color -> x) -> x -> Plant -> x
--            \_____ _____/    \____ _____/    |      |      |
--                  v               v          v      v      v
--                stalk           blossom     leaf  tree  output

Мы видим, что есть часть stalk, а также часть blossom и часть leaf. Мы назовем функцию stalk s и функцию blossom b здесь, а часть leaf l. Чтобы упростить (и оптимизировать) функцию, мы распакуем эти три параметра, а затем вызовем рекурсивный метод:

fold_plant s b l = fold_plant'
    where fold_plant' = ...

Теперь вопрос, конечно, что делать с fold_plant'. Учитывая, что мы видим Leaf, нам не нужно выполнять какие-либо операции со значениями, мы просто возвращаем наш конечный результат l:

fold_plant' Leaf = l

Если мы найдем (Blossom c) с c цветом, мы должны выполнить сопоставление c :: Color с x с частью b, чтобы получить новое значение:

fold_plant' (Blossom c) = b c

Наконец, если у нас есть Stalk, нам придется выполнить рекурсию: сначала мы вызываем fold_plant' на левом стебле, а затем мы вызываем fold_plant' и строим s с двумя результатами:

fold_plant' (Stalk lef rig) = s (fold_plant' lef) (fold_plant' rig)

Таким образом, мы можем объединить все это в следующую функцию:

fold_plant s b l = fold_plant'
    where fold_plant' Leaf = l
          fold_plant' (Blossom c) = b c
          fold_plant' (Stalk lef rig) = s (fold_plant' lef) (fold_plant' rig)

Свертка — это функция, которая берет часть данных в структуре и сворачивает ее в другую часть данных. Обычно мы делаем это, чтобы «свести» коллекцию к одному значению. Вот почему, если вы посмотрите на другие языки, такие как Lisp, Smalltalk, Ruby, JavaScript и т. д., вы найдете эту операцию, называемую reduce, которая является бедным родственником свертки в Haskell.

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

Таким образом, мы можем говорить об «использовании сложения со сгибом для преобразования списка чисел в значение суммы», или мы можем говорить об «использовании функции для получения генеалогического дерева имен и свертывания его в список» и так далее. и так далее. Всякий раз, когда у нас возникает идея изменить структуру чего-либо на одно значение или, может быть, на другой структурированный набор значений, это свертывание.

«Каноническим» способом представления этого в Haskell является foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b, но это проще, как если бы вы думали использовать «список a» в качестве типа Foldable f => t a в начале, потому что его немного легче понять. Итак, у нас есть специальный тип foldr :: (a -> b -> b) -> b -> [a] -> b. Но что такое a и b? а что такое (a -> b -> b) и что делают эти три аргумента?

Давайте настроим его на Int значений как для a, так и для b: foldr :: (Int -> Int -> Int) -> Int -> [Int] -> Int вау... это делает его... интересным, не так ли? поэтому foldr принимает функцию из двух целых чисел, например, функцию (+), и принимает одно значение Int (это начальное значение, которое будет использоваться в качестве целевого результата, и список значений Int... тогда это' ll создаст один Int из этого... то есть он берет эту функцию Int -> Int -> Int и применяет ее к одному Int и первому из [Int], затем применяет эту функцию к этому результату и следующему значению [Int] и так далее и и так далее, пока не останется [Int]... тогда это то, что он возвращает.

Это буквально складывание функции по структуре данных.

Это все хорошо для списков, которые представляют собой одну прямую линию, но у вас есть дерево, а не список. Так как же это там работает? Что ж, давайте посмотрим, как мы могли бы специализировать foldr для получения пары самых высоких и меньших чисел из списка Int вместо этого? foldr :: (Int -> (Int, Int) -> (Int, Int)) -> (Int, Int) -> [Int] -> (Int, Int). Итак, мы берем функцию, которая принимает Int и пару, и помещаем в нее начальную пару вместе с первым Int из нашего [Int]. Это возвращает нам новую пару, и мы затем выполняем тот же процесс для следующего из [Int], а затем продолжаем этот процесс до тех пор, пока в конце не останется только пара.

foldToMinMax = foldr (\newNum (minnum,maxnum) -> (min minnum newNum, max maxnum newNum)) (maxBound :: Int, minBound :: Int)

Итак, теперь все становится немного яснее.

А как насчет этого цветочного дерева, которое у тебя есть? Что ж, вам нужно написать себе функцию складывания, которая будет принимать два значения, одно из которых будет тем же значением, что и начальное значение, и значение результата, а другое из которых будет типом вашего дерева, и построить значение типа результата. Если бы мне пришлось использовать псевдокод для более описательного описания типов, я бы, вероятно, написал что-то вроде: foldr :: (contentOfCollectionType -> resultType -> resultType) -> resultType -> (collectionWrapper contentOfCollectionType) -> resultType

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

Если вы хотите узнать о рекурсии, свертывании и многом другом, но еще не понимаете этих вещей, я рекомендую книгу, автору которой я помогал. http://happylearnhaskelltutorial.com Это объясняется гораздо более подробно и с множеством наглядных примеров. Если вы понимаете основы, вы должны довольно быстро освоиться в том месте, где вы хотите узнать о рекурсии и свертывании... но если вы этого не сделаете, вам будет очень полезно понять основы, потому что вам нужно знать их, прежде чем переходить к другим вещам.

Я должен упомянуть, что ваша конкретная складка также имеет функцию преобразования. Это то, что преобразует Color в x. Функция, с которой вам было дано работать как функция складывания, "сжимает x вместе" (т.е. принимает два значения x и выдает другое значение x, очень похожее на (+) в наших примерах выше). Он может работать только с деревьями, потому что мы также даем ему эту функцию для преобразования Color в x, что эффективно извлекает значимые данные из дерева и помещает их в форму, которую может использовать функция свертки.

Здесь работает очень красивый узор.

Удачи!

Сворачивание — суть рекурсивного решения задач:

    data Plant =                        data Result r =    
         Leaf                                RLeaf 
       | Blossom Color                     | RBlossom Color
       | Stalk Plant Plant                 | RStalk r r
            -- recursive data           -- non-recursive data: `r`, not `Result r`!

Рекурсивное решение проблем заключается в объединении простым способом результатов рекурсивной обработки составляющих исходной структуры:

    -- single-step reduction semantics:
    -- reduction_step :: ..... -> Result r -> r
    reduction_step :: (r -> r -> r) -> (Color -> r) -> r -> Result r -> r
    reduction_step s b l  RLeaf       = l
    reduction_step s b l (RBlosom c)  = b c
    reduction_step s b l (RStalk x y) = s x y

Но чтобы добраться до этого пункта, нам нужно вернуться к составным частям нашей исходной структуры, которые имеют ту же природу, что и вся структура, и, таким образом, fold_plant процедура, которую мы пытаемся создать, может быть применена к ним, как если бы она была уже написана (< em>рекурсия!):

    recurse_into :: (r -> r -> r) -> (Color -> r) -> r -> Plant -> Result r
    recurse_into s b l Leaf          = RLeaf
    recurse_into s b l (Blossom c)   = RBlossom c
    recurse_into s b l (Stalk lt rt) = RStalk (fold_plant s b l lt) (fold_plant s b l rt)

Итак, наконец, наша складка — это просто композиция двух,

    fold_plant :: (r -> r -> r) -> (Color -> r) -> r -> Plant -> r
    fold_plant s b l plant = reduction_step s b l          --          Result r -> r
                               (recurse_into s b l plant)  -- Plant -> Result r

Следите за типами и убеждайте себя, что все сходится как надо.

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

(см. схемы рекурсии).