Производитель банкнот в Haskell

Question

Я изучал Haskell и успешно создал алгоритм для разложения определенной денежной стоимости в банкнотах, которая потребовалась бы для суммирования этой стоимости. Лучшее объяснение (и саму задачу) можно найти здесь .

import Text.Printf
import Data.List
import Data.Ord

filterNearest :: Int->(Int->Bool)
filterNearest a = (\x -> (max a x) <= a)

findNearest :: Int->[Int]->Int
findNearest x possibilities = last $filter (filterNearest x) possibilities

decomposeOnce :: Int->[Int]->[Int]->[Int]
decomposeOnce x list possibilities = [findNearest x possibilities] ++ list

decomposeRecursive :: Int->[Int]->[Int]->[Int]
decomposeRecursive x list possibilities = if x /= 0
    then
        let decomposed = decomposeOnce x list possibilities
        in decomposeRecursive (x - decomposed!!0) decomposed possibilities
    else list

countGroup :: [Int]->(Int, Int)
countGroup list = (list!!0, length list)

makeGroups :: [Int]->[(Int, Int)]
makeGroups list = map countGroup $group list

hasGap :: [(Int, Int)]->(Int->Bool)
hasGap dta = (\idx -> not $any (==idx) $map fst dta)

findGaps :: [(Int, Int)]->[Int]->[Int]
findGaps dta required = filter (hasGap dta) required

fillGaps :: [(Int, Int)]->[Int]->[(Int, Int)]
fillGaps dta gaps = dta ++ map (\x -> (x, 0)) gaps

sortData :: [(Int, Int)]->[(Int, Int)]
sortData dta = reverse $sortBy (comparing fst) dta

calc :: Int->[(Int, Int)]
calc x = let dta = makeGroups $decomposeRecursive x [] [1, 2, 5, 10, 20, 50, 100]
         in sortData $fillGaps dta $findGaps dta [1, 2, 5, 10, 20, 50, 100]

formatData :: (Int, Int)->String
formatData dta = (show $snd dta) ++ " nota(s) de R$ " ++ (show $fst dta) ++ ",00\n"

main = do
    x <- readLn
    print x
    printf $intercalate "" $map formatData $calc x

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

findNearest :: Int->[Int]->Int
findNearest x possibilities = last $filter (filterNearest x) possibilities

Почему я не могу сделать last.filter (filterNearest x) possibilities?

sortData :: [(Int, Int)]->[(Int, Int)]
sortData dta = reverse $sortBy (comparing fst) dta

Почему я не могу сделать reverse.sortBy comparing.fst dta?

Я неправильно понял концепцию?

Answer 1

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

Во-первых, функция приложения . Он определяется следующим образом:

f $ x = f x

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

last $ filter (filterNearest x) possibilities

Сравните с определением оператора $: в вашем коде f равно last, а x равно filter (filterNearest x) possibilities. Следовательно, ваш код эквивалентен этому:

last (filter (filterNearest x) possibilities)

Теперь давайте посмотрим на композицию функций . Он определяется следующим образом:

f . g = \y -> f (g y)

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

Теперь взгляните на ваш предпринятый код:

last . filter (filterNearest x) possibilities

Сравните с определением: f is last и g равно filter (filterNearest x) possibilities. Важно отметить, что второй аргумент filter (filterNearest x) possibilities - это , а не функция ! Поэтому неудивительно, что его нельзя составить с помощью композиции функций.

Но ваша интуиция на самом деле верна (или это ваше домашнее задание?): Композиция функций действительно может использоваться в этом контексте и приносить некоторую пользу.

Давайте посмотрим на это выражение:

last . filter (filterNearest x)

Сравните с определением: f равно last и g равно filter (filterNearest x). Теперь оба аргумента фактически являются функциями, и, следовательно, можно применять композицию функций. Чтобы увидеть результат его применения, просто используйте подстановку:

   last . filter (filterNearest x)
== \y -> last (filter (filterNearest x) y)

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

findNearest :: Int -> [Int] -> Int
findNearest x = last . filter (filterNearest x)

Видите, что спасло вас от композиции функций? Теперь вам не нужно выписывать второй параметр! Большинство Haskell программистов сочли бы это преимуществом, но я также знаю некоторых людей, которые не одобряют это, утверждая, что это делает программу менее понятной. Каждому свое, но полезно отметить это несогласие.

Я оставлю подобное преобразование sortData в качестве упражнения.

Answer 2

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

decompose = f [100, 50, 20, 10, 5, 2, 1]
  where f (coin:coins) value = (value `div` coin) : f coins (value `rem` coin)
        f [] _ = []

Способ решения проблемы слишком сложен , Вместо этого начните с самой большой монеты, рассчитайте, как часто она подходит и сколько осталось, затем повторите со второй по величине монетой и т. Д.