How function reduction in Haskell works?

  • A+
Category:Languages

Why it's possible to reduce function in Haskell:

calculate :: Integer -> Integer -> Integer calculate a b = f 1 a b   where      f :: Integer -> Integer -> Integer -> Integer      f a b c = a + b 

into something:

calculate :: Integer -> Integer -> Integer calculate = f 1   where      f :: Integer -> Integer -> Integer -> Integer      f a b c = a + b 

I just need some guidance, any resources where I can find the answer and read more about it would be really helpful.

 


In Haskell there are no functions that take more than one parameter. All functions take exactly one parameter.

So if you have a function like add :: Int -> Int -> Int, then this is actually short for add :: Int -> (Int -> Int).

Why are the brackets important? Because they show how this concept works. If we have this function add, then we can make a function application with for example 14, then we construct a new function, like:

add14 :: Int -> Int add14 = add 14 

so that means that we now have a function that takes again one parameter (here an Int), and now it will produce another Int, it does that by adding 14 to it, so add14 25 will result in 39.

If you write add 14 25, this thus is not a function application with two parameters, what you actually wrote is:

-- add 14 25 is equivalent to (add 14) 25 

You thus first make a call with 14, and the you make a call with the function that comes out of this, and 25 as the parameter.

Why is this important? Because it means that if you thus write

calculate = f 1 

it means that your f 1, constructs a function, a function with signature Int -> (Int -> Int). Creating parameters in the head of calculate, and adding these to the end of f 1, thus makes no sense: you already constructed a function that takes such parameters anyway. So it only introduces noise.

In lambda calculus, the rewrite rule where one rewrites λ x . f x to just f is (and vice versa) is called η-conversion [wiki]. In Haskell it comes down to rewriting:

f x = g x 

to:

f = g 

Operators are no different. In fact if you write a + b in Haskell, you wrote (+) a b, with (+) a function, or more verbose ((+) a) b.

The f in the where clause:

f a b c = a + b 

can for example get converted to:

f = (.) ((.) const) (+) 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: