8

How do I best map over all elements of a list, except for the last list element?

Say we have a list let l = [1,2,3,4] and want to get [2,3,4,4].

I do have a solution, but it doesn't feel like the "functional" way to do it (in ghci):

let l = [1,2,3,4]
let len = toIntegral $ length l -- to avoid a type mismatch Integer <-> Int
let l1 = zip l [1..]
let l2 = map (\(x,y) -> if y < len then (x + 1,y) else (x,y)) l1
let l3 = map (fst) l2

Not very nice...I do hope there is a better way! Since I'm a novice in functional programming, I don't know where to start looking for it though.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
mort
  • 12,988
  • 14
  • 52
  • 97

5 Answers5

15

Just re-write map but make a special case when there's only one element:

mapBut1 :: (a -> a) -> [a] -> [a]
mapBut1 f [] = []
mapBut1 f [x] = [x]
mapBut1 f (x:xs) = f x : mapBut1 f xs

This will now work even for infinite lists, it's a lot faster than calculating the length, and makes it more readable. Note that this does restrict your function to be of type a -> a instead of a -> b.

Alternatively, you could do

mapBut1 f (x:y:xs) = f x : mapBut1 f (y:xs)
mapBut1 f other = other

They're equivalent definitions, but the latter uses 1 fewer pattern matches. I would prefer the former, though, since it's more immediately obvious what cases are being handled.

bheklilr
  • 53,530
  • 6
  • 107
  • 163
  • Very nice! Just one minor thing: shouldn't the `xs` in the very last line of your code be an `x`, since we are matching a list of length 1? – mort Sep 15 '14 at 17:05
  • 2
    @mort firstly, Haskell doesn't care what we name the variables, so renaming `xs` to `x` won't change the meaning of the code. Secondly, that line is matching anything that didn't match the pattern `(x:xs)`, which could be `[_]` or `[]` (`[_]` indicates a list of one element). So what it's saying is that anything other than the pattern `(x:xs)` would be matched, not that a single element would be. However, you did make me spot a small bug I have in this code. – bheklilr Sep 15 '14 at 17:08
10

This is a job for pretend-paramorphism, as usual:

import Data.List (tails)

mapButLast :: (a -> a) -> [a] -> [a]
mapButLast f = foldr g [] . tails where
  g (x:_:_) r = f x : r
  g xs      _ = xs

Or with proper para we'd just write

mapButLast f = para g [] where
  g x [] r = [x]
  g x _  r = f x : r

where

para f z (x:xs) = f x xs (para f z xs)
para f z []     = z
Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • 3
    That's a nice pattern! – J. Abrahamson Sep 15 '14 at 17:31
  • @J.Abrahamson I've edited some more in, with a link. ;) – Will Ness Sep 15 '14 at 17:32
  • `para` is the "obvious" way, but I like the idea of using `tails` to get a pretend-para. Though, with them both side by side I'm less certain it's actually that much *more* intelligible than `para` itself. – J. Abrahamson Sep 15 '14 at 17:46
  • 1
    @J.Abrahamson ultimately they are the same - access to `tails` is what `para` does (up to one skipped beat). with `tails` it even gets to reuse structure. Sometimes the non-standard `para f z [] = z; para f z xs@(x:t) = f x xs (para f z t)` might be preferable, and that's exactly the `foldr ... tails` variant. – Will Ness Sep 15 '14 at 19:19
  • oh, and [nothing is new under the sun](http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm#maplist). – Will Ness Sep 15 '14 at 19:33
  • Yep, agreed. I'd just not seen it written out in this form before. – J. Abrahamson Sep 15 '14 at 21:22
4

You can also use init and last from standard librairies (no special import) if you don't care about performances.

you can write

map f (init list) ++ [last list]

where

  • f : function you want to map
  • list : list you want to map over
Rvion
  • 124
  • 5
  • This is not *that* bad performance-wise as `init` is lazy and `last list` expr. is in WHNF before evaluated. I'd bet it's on par with the accepted answer by O(n) traversing to the last elem which may be well optimized by ghc. – David Unric Sep 15 '14 at 17:56
  • 1
    @DavidUnric, this has pretty bad performance characteristics. In particular, it is not a good streamer: it will keep the whole input list in memory until the last element is evaluated. – luqui Sep 15 '14 at 19:29
  • 1
    I like this solution because it's readable even for beginners ;) – mort Sep 15 '14 at 19:37
1

What makes this last element so special?

I know it does not answer your question, but I'd consider a type like 

data Foo a = Foo a [a]

and an appropriate Functor.

Jean-Baptiste Potonnier
  • 568
  • 3
  • 8
0

I just want to add an alternative using list comprehension and an attempt to compare the solutions (first time I try it so let me know if I didn't do it right)

reverse $ last l : [f x | x <- tail (reverse l)]

It is slower than most of the other solutions (see report link below).

Here is a sample program (allbutlast.hs). It has all the above solutions, a simple quickcheck test and a benchmark using criterion.

Prerequisites to run: QuickCheck and criterion

cabal update
cabal install QuickCheck
cabal install -j --disable-tests criterion

Execution

ghc -O2 --make allbutlast.hs
./allbutlast --output allbutlast.html

Sample report: Criterion report for allbutlast

monk
  • 640
  • 1
  • 5
  • 17