2

I want to return the preceding element of an element in list. I am intending to get the index of parameter and use it to deprecate list such that parameter is the last element, then reverse it and take the second element of reversed list. I get error: type elemIndex is Maybe Int while take function require Int. I want to fix it or write code using simple recursion Are there a shorter code using recursion?

precedingElement :: Eq a => a -> [a] -> Maybe a
precedingElement elt lst    | lst == [] = error "List is empty"
                            | elt `notElem` lst = Nothing
                            | otherwise = Just x where x = snd (reverse (take (elt `elemIndex` lst) lst))
GlossMash
  • 89
  • 8
  • I have answered the question in your title. However, much of the rest of your question is difficult to understand. I'm not sure what "I am intending to get the index of parameter and use it to deprecate list such that parameter is the last element, then reverse it and take the second element of reversed list." means. I suggest that you break this down into small pieces and write code for each piece separately. As you build up your code, you will eventually get a complete solution. – Code-Apprentice Aug 16 '16 at 01:33

4 Answers4

9

One of my favourite underappreciated utilities is rather handy for problems like this. Let me have backward lists, so I don't need to reverse my brain.

data Bwd x = B0 | Bwd x :< x  -- rightmost is nearest

Think of list elements as the beads on an abacus wire. Flick a few to the left and leave your finger resting on the next one. What have you? A list of beads to the left of your finger (with the rightmost nearest), a list of beads to the right of your finger (with the leftmost nearest), and the bead with your finger on it.

That is, a one-hole element context for lists is given by the pair of backward and forward lists either side of the hole.

type ListContext x = (Bwd x, [x])

Those who know my old songs recognize ListContext as the derivative of [].

An element in focus (your finger on a bead) is

type ListFocus x = (ListContext x, x)

And there is a useful operation which decorates every list element with its context, putting it in focus.

focus :: [x] -> [ListFocus x]
focus = go B0 where
  go xz [] = []
  go xz (x : xs) = ((xz, xs), x) : go (xz :< x) xs

For example,

focus [1,2,3] = [((B0,[2,3]),1), ((B0 :< 1,[3]),2), ((B0 :< 1 :< 2,[]),3)]

and now it is very easy to answer all sorts of questions that concern an element and its immediate surroundings. You mightn't construct focus just to solve this problem, but it's the sort of thing I keep around because it solves lots of problems.

[p | ((_ :< p,_),q) <- focus xs, q == x]

computes all the values p which sit to the left of an x in xs. As you can see.

(By the way, this focus operation didn't come from nowhere. It arises from the differential structure of the datatype of lists. This answer (where it is called picks) tells the list story in more detail, and this answer develops the datatype generic story.)

Community
  • 1
  • 1
pigworker
  • 43,025
  • 18
  • 121
  • 214
5

In order to return the preceding element of the given element, you can use some pattern matching and recursion:

precedingElement _ [] = Nothing
precedingElement _ [x] = Nothing
precedingElement elt (x:y:rest)
    | y == elt = Just x
    | otherwise = precedingElement elt (y:rest)
Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268
2

As I'm a big fold fan, I might write something like

lastBefore :: (a -> Bool) -> [a] -> Maybe a
lastBefore p xs = foldr go (`seq` Nothing) xs Nothing
  where
    go x r (Just prev) | p x = Just prev
    go x r _ = r (Just x)

But I'd have to check that GHC optimizes it as I wish.

dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • 1
    This looks slick. I'm really starting to like these. One question though: why ```(`seq` Nothing)``` and not `(const Nothing)`? – Alec Aug 16 '16 at 03:48
  • Note that `lastBefore (==0) [0,1,0,2,3]` will return `Just 1` unlike the answer by Code-apprentice. Changing either answer to behave as the other one is trivial, though. (Still, I'm not yet a fan of the foldr-with-four-arguments pattern -- even if I do use it sometimes.) – chi Aug 16 '16 at 06:28
  • @Alec, it may not matter, but I've learned that making strictness very consistent can help the optimizer. Using `seq` there ensures that the `Maybe` produced will always be demanded. That may or may not ever matter, but it makes me feel better. – dfeuer Aug 16 '16 at 15:58
1

Sort-of standard solution for this is to use zipping:

import Data.List (find)

preceding :: (a -> Bool) -> [a] -> Maybe a
preceding f xs = fmap snd . find (f . fst) $ zip (drop 1 xs) xs
user6722421
  • 11
  • 1