Haskell Caching

Question

After solving a problem on Project Euler I came across the following Haskell code in the forum:

fillRow115 minLength = cache where cache = ((map fillRow115' [0 ..]) !!) fillRow115' 0 = 1 fillRow115' cells = sum (map cache [0..cells-minLength]) + cache (cells-1)

I just started learning Haskell this week and can't seem to understand this code. Can somebody please explain the following 2 items:

To me it looks like there is only one argument minLength, but the function requires 2 arguments to run in ghci. Where does this other argument come into play?
From what I've been able to find online, !! is the list index operator and returns the nth element when called as [list] !! n. The code above seems to call it with only one argument. What is that doing?

P.S. If anyone is thinking of copying this code to solve the Project Euler problem, it doesn't seem to give the correct answer.

Thomas M. DuBuisson · Accepted Answer · 2013-07-04 20:50:56Z

Where does this other argument come into play?

Lets simplify this question even further. You probably know about the head function:

head [] = error "something bad" head (x:_) = x

You could be silly and define your own head function that just calls head:

myHead xs = head xs

And notice both the left and right side apply the variable xs, so we can do what's called eta-reduction and result in:

myHead = head

Type signatures might hammer the point home:

myHead :: [a] -> a myHead = (head :: [a] -> a)

So in your case, fillRow115 takes a second argument because it is equal to cache, which takes an argument - and that brings us to your second question.

The code above seems to call it with only one argument. What is that doing?

Consider the function +. If you wish to make a function that always adds 2 you can "partially apply" 2 to the function +:

addTwo = (+2) -- (2+) would work just as well

So you are looking at the list indexing function !!:

(!!) :: [a] -> Int -> a

And saying to yourself, that is only being applied to some list. Applying what we know about partial application we get a type of:

(someList !!) :: Int -> a

So that is in fact a function from Ints to an element of the list.

If this doesn't click yet, just replace someList with the list you are using:

someList = map fillRow115' [0..] (someList !!) === ((map fillRow 115' [0..]) !!)

Alexander · Accepted Answer · 2013-07-06 19:11:15Z

This concept is called partial application .
It works because in Haskell, all functions actually only have one parameter.
A function a -> b -> c might look like a function that takes two parameters
(one of typa a, and one of type b), but it's really a function a -> ( b -> c),
i.e. a function with one paramater (of type a) that returns a function that takes a parameter (of type b).

See http://www.haskell.org/haskellwiki/Partial_application
(or just generally, give http://learnyouahaskell.com/ a go)

Collectives™ on Stack Overflow

Haskell Caching

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related