I've started studying Haskell a while ago and during my exams I was asked to answer what cost function would return if it was called but I couldn't understand which steps would occur. I'm sitting the exams again but I couldn't manage to understand the way I should solve this type of programs.
Any help would be appreciated!
cost = n(twice, inc, 3)
n(h,s,x) = if (x<1) then (h s x) else n(h, (h s), x-1)
inc x = x+1
twice n a = n (n a)
Type signatures would really go a long way here. Let's start with the simplest one, inc:
inc :: Num a => a -> a
inc x = x + 1
This is easy to derive because + 1 has type Num a => a -> a, and you can check this in GHCi with :type (+1). Next, let's look at the function twice. It's obvious that the n passed in has to be a function, since it's applied to both a and n a. Because it's applied to n a and a, both of these expressions must have the same type, and n must have only one parameter, so we can say that twice has the type
twice :: (a -> a) -> a -> a
twice n a = n (n a)
Now we can figure out n. It takes a tuple (h, s, x) as an argument and is called recursively. h has to be a function of two arguments, since it's applied to s and x, and s is unknown without more context. x has to be both a Num a => a and an Ord a => a due to its use with < 1 and -1, so we can write the signature as
n :: (Num a, Ord a) => (b -> a -> c, b, a) -> c
n (h, s, x) = if x < 1 then h s x else n (h, h s, x - 1)
Notice that I removed some unnecessary parens here. Finally, we can figure out the type of cost, which is simply n's return type:
cost :: (Num a, Ord a) => a
cost = n (twice, inc, 3)
But what would this return? For starters, it's re-write n's definition but with twice, inc, and 3 substituted in:
if 3 < 1
then twice inc 3
else n (twice, twice inc, 3 - 1)
Obviously 3 < 1 is false, so let's reduce n (twice, twice inc, 3 - 1):
if 2 < 1
then twice (twice inc) 2
else n (twice, twice (twice inc), 2 - 1)
Same story here, 2 < 1 is false, so let's continue to reduce:
if 1 < 1
then twice (twice (twice inc)) 1
else n (twice, twice (twice (twice inc)), 1 - 1)
Nothing new on this step, one more try:
if 0 < 1
then twice (twice (twice (twice inc))) 0
else n (twice, twice (twice (twice (twice inc))), 0 - 1)
Here we have 0 < 1, so we then choose the branch of twice (twice (twice (twice inc))) 2. To solve this, just plug in inc and 0 into the definition of twice:
twice (twice (twice (twice inc))) 0
= twice (twice (twice (inc . inc))) 0
= twice (twice (inc . inc . inc . inc)) 0
= twice (inc . inc . inc . inc . inc . inc . inc . inc) 0
= (inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc) 0
= 16
And we now can't reduce this expression any more! So the entire chain of reductions is
cost = n (twice, inc, 3)
= if 3 < 1
then twice inc 3
else n (twice, twice inc, 3 - 1)
= n (twice, twice inc, 2)
= if 2 < 1
then twice (twice inc) 2
else n (twice, twice (twice inc), 2 - 1)
= n (twice, twice (twice inc), 1)
= if 1 < 1
then twice (twice (twice inc)) 1
else n (twice, twice (twice (twice inc)), 1 - 1)
= n (twice, twice (twice (twice inc)), 0)
= if 0 < 1
then twice (twice (twice (twice inc))) 0
else n (twice, twice (twice (twice (twice inc))), 0 - 1)
= twice (twice (twice (twice inc))) 0
= inc (inc 0)
= inc (0 + 1)
= (inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc) 0
= 16
(To keep things readable I've used twice f = f . f instead of twice f x = f (f x), but these definitions are equivalent)