haskell - Haskell 中的钞票找零机

Question

我一直在研究 Haskell，并成功地制定了一种算法来分解纸币中给定的货币值(value)，并计算出该值(value)的总和。可以找到更好的解释(以及挑战本身)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)possibility？

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

为什么我不能reverse.sortBy Comparison.fst dta？

我的概念有误吗？

Answer 1

函数组合.与函数应用$不同。您不能将 $ 替换为 . 并期望程序具有相同的含义。它们是不同的东西。

一、函数应用。它的定义如下:

f $ x = f x

该运算符在左侧接受一个函数，在右侧接受一个值，并且仅将值作为参数传递给函数。以您的表达为例:

last $ filter (filterNearest x) possibilities

与运算符$的定义进行比较:在您的代码中，f是last，x是过滤(filterNearest x)可能性。因此，您的代码相当于:

last (filter (filterNearest x) possibilities)

现在，让我们看看函数组合。它的定义如下:

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

这意味着组合两个函数 f 和 g 的结果是另一个函数，它将其参数传递给 g 然后将 g 的返回值传递给 f。

现在看看您尝试的代码:

last . filter (filterNearest x) possibilities

与定义比较:f 是last，g 是过滤器(filterNearest x)可能性。这里需要注意的重要一点是，第二个参数filter (filterNearest x)possibility不是一个函数!所以难怪它不能通过函数组合来组合。

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

让我们看一下这个表达式:

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 的类似转换作为练习。