CODEWITHSUNDEEP
haskelltrace
Nanc
Nanc

Reputation: 464

Haskell - Result of a program

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)

Upvotes: 2

Views: 168

Answers (1)

bheklilr
bheklilr

Reputation: 54058

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)

Upvotes: 6

Related Questions