[Haskell-cafe] defining mapPairs function

[Dan Weston]

Sometimes it is interesting to approach things from a different 
perspective. The goofyness below will have been useful if it interests 
you in point-free programming. And anyway, I sure had a good time 
writing it...

I am composing several common Haskell idioms:

1) When adjacent list elements are paired is (duplicate,offset one of 
them, zip together):

   Prelude> let z = [2,3,5] in zipWith (*) z (tail z)
   [6,15]

2) Uninterleaving (slicing) a list:

   Prelude> let slice = fst . foldr (\a ~(x,y) -> (a:y,x)) ([],[])
   Prelude> slice [1..10]
   [1,3,5,7,9]

   For fun, I will do the slicing by changing the odd-indexed elements 
to  Just x, and the even ones to Nothing, then filter only the Justed 
elements.

There is a twist in your problem: do something special with the last odd 
(orphaned) element, i.e. append it. One thing to watch out for is that 
functions like head, tail, last are partial functions that don't play 
well with the empty list. In my case, I forstall disaster by prepending 
an unused Nothing value to my list before calling last.

For comparison with your concise solution, below is my much more 
obfuscated one. Believe it or not, this algorithm was the first one that 
popped into my head. I have encoded it in point-free notation so that it 
reads along with its algorithm description (and because it's so much fun!)

If the use of &&& and >>> is new to you, just read through to get a 
taste of how it can be used. Note that there is no variable name 
anywhere in the code, only functions!

Solving the same problem several different ways will help build your 
toolbox. I am not recommending my solution for your exam (it's longer 
and less efficient than yours), only pointing out that there is always 
more than one way to do something in Haskell.  :)


import Control.Arrow((&&&),(>>>))
import Data.Maybe(catMaybes,maybeToList)

mapPair = (id &&& tail           >>>  -- offset list by one
            uncurry (zipWith (*)) >>>  -- multiply adjacent
            alternate             >>>  -- mark   even elements
            catMaybes)                 -- delete even elements

                  &&&                  -- Tuple this up with...

           (alternate             >>>  -- keep odd indices
            (Nothing:)            >>>  -- make sure there is a last
            last                  >>>  -- get last
            maybeToList)               -- keep if it had odd index

                  >>>                  -- and then...

           uncurry (++)                -- append pair of lists

   where alternate = zipWith ($) (cycle [Just,const Nothing])
                   -- Mark even-indexed elements for deletion
                   -- cycle goes on forever, but zipWith stops at
                   -- the end of the shorter list, so no worries.

In this formulation, you can see that the whole second half above is 
there just to handle the orphaned last element, suggesting that there is 
something unnatural in the problem specification (probably put there to 
keep you from just using zipWith!).

Here is a worked example for [2,3,5,7,11] in case you're not used to 
point-free programming:

  (id &&& tail           >>>  -- ([2,3,5,7,11],[3,5,7,11])
   uncurry (zipWith (*)) >>>  -- [6,15,35,77]
   alternate             >>>  -- [Just 6,Nothing,Just 35,Nothing]
   catMaybes)                 -- [6,35]
                  &&&
  (alternate             >>>  -- [Just 2,Nothing,Just 5,Nothing,Just 11]
   (Nothing:)            >>>  -- [Nothing,Just 2,Nothing,Just 5,
                              --  Nothing,Just 11]
   last                  >>>  -- Just 11
   maybeToList)               -- [11]
                  >>>         -- ([6,35],[11])
  uncurry (++)                -- [6,35,11]


Dan Weston

Alexteslin wrote:
> 
> 
> Alexteslin wrote:
>> Hello,
>>
>> I just came across with this question on the exam and can not think of
>> implementing it.
>>
>> mapPair :: (a -> a -> a) -> [a] -> [a]
>>
>> such that mapPairs f [x1, x2, x3, x4...] = [f x1 x2, f x3 x4,...]
>>
>> and if the list contains an odd number of elements, the last one is kept
>> unchanged, for example
>>
>> mapPairs f [x1, x2, x3] = [f x1 x2, x3]
>>
>>
>> Any ideas will be appreciated, thanks
>>
> 
> Oh, I think i just defined it - seems to work.
> I spent some time on the exam and made silly mistakes:
> 
> mapPairs :: (a -> a -> a) -> [a] -> [a]
> mapPairs f [x] = [x]
> mapPairs f [] = []
> mapPairs f (x:xs) = f x (head xs) : mapPairs f (tail xs)
> 
> I was concing f x to (head xs) as well and 
> mapPairs f [x] = x  - this is very silly mistake.
> 
> Does anyone think this is the right answer?
>