Zipping Half of a List with Its Reversal

I found this note with one page of Haskell code, without comments, when I was cleaning up my files. It took me quite a while to figure out what it might probably be about: given a list, zip its first half with the reverse of its second half, in only “one and a half” traversals of the list. It gives us a fast algorithm to, for example, check whether a list is a palindrome. I thought it was probably something we discussed in AoP, but it turns out that I must have taken the note when people in IPL were studying There and Back Again of Danvy and Goldberg. Recorded in the note was my attempt to understand it.

Let convolute (xs,ys) = zip xs (reverse ys) and half be a function cutting a list in half, the problem is simply specified by revzip = convolute . half. The first trick is that convolute can be expressed in terms of its generalisation:

> convolute :: ([a],[b]) -> [(a,b)]
> convolute = fstn . uncurry walk
>   where fstn (xs,[]) = xs

where walk is defined by:

  walk xs ys = (zip xs (reverse (take n ys)), drop n ys)
      where n = length xs

The reason introducing walk is that it can be defined as a fold:

> walk = foldr ((.).shift) (split (nil, id))
> shift x (zs,y:ys) = ((x,y):zs, ys)
> nil _ = []

But the definition below is probably a lot more comprehensible:

  walk [] ys = ([],ys)
  walk (x:xs) ys = shift x (walk xs ys)

Some of these auxiliary functions should be part of the Haskell Prelude:

> prod (f,g) (a,b) = (f a, g b)
> split (f,g) a = (f a, g a)

The following implementation of half splits a list into two halfs using two pointers:

> half :: [a] -> ([a],[a])
> half = race . dup 
> race (xs,[]) = ([],xs)
> race (_:xs,[_]) = ([],xs)
> race (x:xs,_:_:ys) = cross ((x:),id) (race (xs,ys))
> dup a = (a,a)

Furthermore, uncurry f = apply . prod (f,id) where

> apply (f,a) = f a

Therefore the specification has become:

  revzip = fstn . apply . prod (walk,id) . race . dup

Now we try to fuse prod (walk,id) . race and get

> wrace (xs,[]) = (split (nil, id), xs)
> wrace (_:xs, [_]) = (split (nil, id), xs)
> wrace (x:xs, _:_:ys) = prod ((shift x .), id) (wrace (xs,ys))

Hence the result:

> revzip = fstn . apply . wrace . dup

4 thoughts on “Zipping Half of a List with Its Reversal

  1. Shin Post author

    Thanks for all the comments. I was not aware of these functions in Control.Arrow. They’d save me lots of typing next time! :)

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>