Disconnected Mutterings of a Random Geek

Tue, 19 Jun 2007

freduce

Since I'm not at Debconf, I've been filling in time in the early mornings by randomly browsing Facebook. Chris Lamb had a post on a function called fnreduce, which clearly wandered past on planet when I was away. Since I was bored, I wrote a simple haskell version:

fnreduce :: [(a->a)]->a->a
fnreduce [] value = value
fnreduce (a:as) value = freduce as $ a value

Line by line, its clear how it works. The first line is the type sig, which says that the function fnreduce takes a list of functions, and a value of type a, and a gives back a value of type a. The functions all need to be of the type a->a, which means they take a a and give back a a. a is a type varible, which means it can be replaced with any type you feel like, for example: Int or String.

The second line merely defines a base case, which says that if the list of functions is empty, it just returns the value given. The last line does all the work, and says that fnreduce on a non-empty list is computed by taking the first element of the list, computing the new value using it, then calling fnreduce on the rest of the list and the new value. This is how most list processing works in haskell.

I'm left with two quick questions: the first is how to define it in terms of a fold, which it clearly is. The second is how to escape the a->a resriction, which lamby's can do. Since I'm writing haskell, I'ld like to do this in a type safe way, to have my cake and eat it too. This cant be done with haskell's type system, but I may run it past Edwin for his two cents if I remember...

posted at: 09:15 | path: /computing/haskell | permanent link to this entry

Made with PyBlosxom