Saturday, January 24, 2009

pairMap revisited

A while ago, I needed a list function similar to a fold, but I wanted to operate always with the current and previous element instead of accumulating a result to operate with the current element (and return a list of the results of each pair operation)

I originally wrote it more or less like this:

def pairMap[A,B](previous:A, aList:List[A], f: (A, A) => B): List[B] = aList match {
case Nil => Nil
case head :: tail => f(previous, head)::pairMap(head, tail, f)
}

I was using it in the context of getting a list of gaps between the numbers of a list:

def getGapList(aList: List[int]) = pairMap(aList.head, aList.tail, (a:Int, b:Int)=>(b - a))

Usage example:

val list = List(2, 5, 9)
list: List[Int] = List(2, 5, 9)

getGapList(list)
res1: List[Int] = List(3, 4)

The other day, reminiscing about the Fibonacci example in "A Gentle Introduction to Haskell Version 98", a different implementation occurred to me. Unsurprisingly, it involves zipping a list with itself 8)

Thinking about folds, I thought I might as well put an initial value.

def pairMapWithInitial[A,B](initial:A, aList:List[A], f: (Tuple2[A, A]) => B):List[B] = {
initial::aList zip aList map f
}

def getGapListWithInitial(initial:int, aList:List[int]) = pairMapWithInitial(initial, aList, (a:Tuple2[Int,Int])=>(a._2 - a._1))

Usage example:

getGapListWithInitial(list.head, list.tail)
res2: List[Int] = List(3, 4)

getGapListWithInitial(0, list)
res3: List[Int] = List(2, 3, 4)

Because it's clearer to me, I still prefer the first version with "match", but it was a nice exercise to explore the zip version.

Post update
A similar version can be written using the List.map2 function which is pretty similar to a zip and map except the function takes two arguments instead of a tuple.

def pairMapWithInitial[A,B](initial:A, aList:List[A], f: (A, A) => B): List[B] = {
List.map2(initial::aList, aList) (f)
}

def getGapListWithInitial(initial:int, aList:List[int]) = pairMapWithInitial(initial, aList, (a:Int, b:Int)=>(b - a))

1 comment:

dibblego said...

Here are a couple of scary words: catamorphism and paramorphism.

A right-fold is the catamorphism for List i.e. the foldRight method forms the catamorphism. What does this mean exactly? You needn't concern yourself too much, however, do observe that foldRight across the Nil and :: constructors produces an identity function:

forall x. x.foldRight(Nil)(_ :: _) == x

Your pairMap function can be written using a paramorphism (from which you can derive a catamorphism for list). This too is nothing too concerning, but is similar to a foldRight except the given function takes another argument - the tail of the list.

Unfortunately, the Scala libraries do not have a para method on List, but there is one in the Scalaz library (see scalaz.control.Paramorphism).

Hope this helps, bye!