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

与定义比较：fislast和gis filter (filterNearest x) possibilities。这里要注意的项重要的事情是，第二个参数filter (filterNearest x) possibilities是不是一个功能！所以难怪它不能通过函数组合来组合。

但事实上，你的直觉是正确的（或者它是你的家庭作业？）：函数组合确实可以在这种情况下使用并提供一些好处。

我们来看看这个表达式：

last . filter (filterNearest x)

与定义比较：fislast和gis 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作为练习。