Banknote change maker in Haskell

Question

I've been studying Haskell and I successfully make an algorithm to decompose a given monetary value in the banknotes it would take to sum this value. A better explanation (and the challenge itself) can be found 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

There is cases that I think I could have used the function composition operator, but I couldn't manage to apply it properly, so I'd like to ask for help for applying function composition is some spots:

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

Why can't I do last.filter (filterNearest x) possibilities?

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

Why can't I do reverse.sortBy comparing.fst dta?

Am I getting the concept wrong?

Answer 1

Function composition . is not the same thing as function application $. You can't swap out $ for . and expect the program to have the same meaning. They're different things.

First, function application. It is defined like this:

f $ x = f x

The operator takes a function on the left side and a value on the right side, and merely passes the value to the function as an argument. Take, for example, your expression:

last $ filter (filterNearest x) possibilities

Compare with definition of the operator $: in your code f is last and x is filter (filterNearest x) possibilities. Therefore, your code is equivalent to this:

last (filter (filterNearest x) possibilities)

Now, let's look at function composition. It is defined like this:

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

This means that the result of composing two functions f and g is another function, which passes its argument to g and then passes g's return value to f.

Now take a look at your attempted code:

last . filter (filterNearest x) possibilities

Compare with the definition: f is last and g is filter (filterNearest x) possibilities. The imporant thing to note here is that the second argument filter (filterNearest x) possibilities is not a function! So no wonder it cannot be composed via function composition.

But your intuition is, in fact, correct (or is it your homework assignment?): function composition can indeed be used in this context and provide some benefit.

Let's take a look at this expression:

last . filter (filterNearest x)

Compare with the definition: f is last and g is filter (filterNearest x). Now both arguments are, in fact, functions, and therefore, function composition can be applied. To see the result of applying it, just use substitution:

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

So the result of such composition is a function that takes a list as a parameter, filters that list, and then takes the last element of the result. So the full definition of findNearest could look like this:

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

See what the function composition saved you? Now you don't have to write out the second parameter! Most Haskell programmers would consider this a benefit, but I also know some people who would frown at this, arguing that this made the program less understandable. To each their own, but useful to note this disagreement.

I'll leave similar transformation of sortData as an exercise.