Haskell: Using already computed part of list to compute further list

I faced a rather difficult (for a functional programming noob anyway) problem while coding in Haskell recently. Say I have a list which needs updating. Flex some FP muscles and you realise that if you have a function to update a single element, like:

updElem :: a -> a
updElem cur = --definition goes here

then the function to update the list of elements is simply defined as:

updList :: [a] -> [a]
updList = map updElem

Pretty simple. A basic observation here is that if we denote original list by Lo and updated list by Lu, then Lu[n] depends on Lo[n]. Now here’s the problem I faced. In my case, Lu[n] depended not only on Lo[n], but also Lu[n-1]. Not a big issue, I say, and proceed to redefine my updElem as

updElem :: a -> a -> a
updElem cur prev = --definition

And what about updList? It gets redefined thusly

updList :: [a] -> [a]
updList (prev:cur:[]) = [updElem cur prev]
updList (prev:cur:rem) = updElem cur prev : updList (cur:rem)

I gave myself 3 gentle pats on the back for coming up with this function and proceeded to test it out. It failed. Big time. Compiler having failed me, I resorted to my favorite debugger – pen and paper! I walked through each recursive call of updList and it wasn’t hard to see why it was bombing out – the pattern match is matching against Lo the whole time and I need my prev to come from Lu, not Lo.

Realizing the problem was but a small part of the solution. Fixing it is where the headache lay. Lu, while being created, needed reference to it’s own previous element to grow further. I guess the main reason I got stuck here was because I got thinking that I needed to access the stack of updList somehow since that is where the state of Lu will be stored while being created.

Several fruitless hours later, I gave up and sought help of the expert minds over at Stack Overflow. When I saw the solution posted there, I banged my head on the nearest wall for each pat I had awarded myself earlier, plus one. Picking up my jaw up from the floor, I proceeded to implement the simplistically brilliant solution which had totally eluded me so far. Here I present to you the final and correct version of updList in all it’s idiomatic glory:

updList :: [a] -> [a]
updList xs = zipWith updElem xs shifted
where shifted = 0 : updList xs

Where comes the magic number 0 from, you ask? Notice how in this entire post I have been silent about what element of the updated list Lu[0] depends on? Well it really depends on your problem. In my case, assuming it depends on 0 is works fine enough. Otherwise, if [a] is a list of your custom data types, perhaps you can introduce a null type constructor to replace the zero.

Advertisements