Haskell 中的零钱机

Question

我一直在研究 Haskell 并且我成功地制作了一种算法来分解纸币中给定的货币价值，以求出该价值的总和。可以找到更好的解释（以及挑战本身）here。

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 的 return 值传递给 f.

现在看看您尝试的代码：

last . filter (filterNearest x) possibilities

比较定义：f是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 [] _ = []

你处理问题的方式太复杂了。相反，从最大的硬币开始，计算它适合的频率和剩余的数量，然后用第二大的硬币重复，依此类推。

Haskell 中的零钱机

Banknote change maker in Haskell

haskell

functional-programming

coin-change