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

Question

Даны два типа данных: Цвет и Растение.

data Color = Red | Pink | White | Blue | Purple | Green | Yellow
   deriving (Show, Eq)

data Plant =
     Leaf
   | Blossom Color
   | Stalk Plant Plant
   deriving (Show, Eq)

Теперь я должен реализовать функцию fold_plant следующего типа:

(x -> x -> x) -> (Color -> x) -> x -> Plant -> x

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

По-видимому fold_plant Stalk Blossom Leaf это личность на растениях.

Теперь я знаю, что в Haskell вы делаете такие функции:

fold_plant :: (x -> x -> x) -> (Color -> x) -> x -> Plant -> x
fold_plant = do something

Но с этого момента я не знаю, как работает функция сгиба на растении.

Answer 1

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

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)

Answer 2

Сгиб - это функция, которая берет фрагмент данных в структуре и сворачивает его в другой фрагмент данных. Обычно мы делаем это, чтобы "уменьшить" коллекцию до одного значения. Вот почему, если вы посмотрите на другие языки, такие как Lisp, Smalltalk, Ruby, JavaScript и т. Д., Вы обнаружите, что эта операция называется reduce, который является бедным двоюродным братом в Хаскелле.

Я говорю, что это плохой родственник, потому что ваша интуиция в списках верна, но в Haskell мы гораздо более абстрактны и общие, поэтому наши функции свертывания могут работать с любым типом структуры, тип которой мы сказали 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 значения... тогда он будет производить один 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 значение, очень похожее на (+) в наших примерах выше). Он может работать только на деревьях, потому что мы также даем ему эту функцию, чтобы повернуть Color в x, который эффективно извлекает значимые данные из дерева и помещает их в форму, которую может использовать функция свертывания.

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

Удачи!

Answer 3

Складывание - это суть решения рекурсивных задач:

    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 Процедура, которую мы стремимся создать, может быть применена к ним, как если бы она уже была написана (рекурсия!):

    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

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

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

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