2
\$\begingroup\$

I'm looking for general review and improvements on this code that safely gets the next element of a list (and wraps to the first element if you exceed the list). It just seems a little excessive for how simple of a task it is. It should also be noted that this function will only work for lists that do not contain duplicate elements. Unless I modify it to take index numbers instead, I can't see that restriction changing. If length list < 2, it will return Nothing.

nextElem :: Eq e => e -> [e] -> Maybe e
nextElem e xs = nextElem' e (shiftList e xs)
    where
        shiftList e xs = let (ya, yb) = break (== e) xs in yb ++ ya
        nextElem' _ []      = Nothing
        nextElem' _ (x : [])= Nothing
        nextElem' e (x : xs)
            | x == e    = Just (head xs)
            | otherwise = nextElem' e xs
\$\endgroup\$
2
\$\begingroup\$

Using functions out of base you can implement this as a fairly readable one-liner.

import Data.Maybe (listToMaybe)

nextElem :: Eq a => a -> [a] -> Maybe a
nextElem e xs = listToMaybe . drop 1 . dropWhile (/= e) $ xs ++ (take 1 xs)

To break that down, since the list is supposed to be "circular" we safely pop the first element off the front of xs with take 1 (we either get the first element, or an empty list) and append that to the back of xs to get the wrapping property. (As an aside, this is complicated a small amount by being efficient, an equally correct solution to having a circular list would be xs ++ xs, but that would end up checking the entire list for equality twice if e isn't present.)

Next we drop all elements from the front of the list that are not equal to e, which either produces the empty list if the element isn't found, or the first tail of the list fronted by e, i.e., (e:...), so we use drop 1 as a safe version of tail (to again handle the case of an empty list) and end up with a list where the head element is our answer. Then listToMaybe produces Just the first element of the list, or Nothing if the list is empty.

In principle this isn't much different from your original solution, I've just shrink-wrapped it down to the constituent pieces and arranged control through function composition.

\$\endgroup\$
  • \$\begingroup\$ Ha. I didn't think that this could be shrunk down to a single line. I'd "staircase" it for readability, but I still like this answer. Thank you. \$\endgroup\$ – Carcigenicate Aug 26 '14 at 0:19
2
\$\begingroup\$

It looks like you are trying to do the same thing in two different ways.

To detect the case where e is not in xs, you should check whether yb is empty. (If that's what you were trying to do with nextElem' _ (x : [])= Nothing then you should note that it doesn't do that.) I'm not sure what the purpose of the otherwise case is. If break didn't find any element equal to e, recursion won't find it, either. Therefore, a simpler solution would be

nextElem :: Eq a => a -> [a] -> Maybe a
nextElem e xs
  | null match = Nothing
  | null rest  = Just (head xs)
  | otherwise  = Just (head rest)
  where
    (skip, match) = break (== e) xs
    rest = tail match

What is the expected result for nextElem something [something] — a one-element list that happens to contain the element you are looking for? I believe you would produce Nothing. I would have expected something instead. If you want to preserve the original behavior, where nextElem 'a' "a" produces 'a', then you could insert

nextElem e [_] = Nothing

as a special case to this solution.

\$\endgroup\$
  • \$\begingroup\$ I think you're confused on a couple points. The function returns the next element of a list, following e. The first where binding is a function that splits the list, and puts the given element at the start, and wraps the rest to the end. I wouldn't say that it's circular, as it's only ever called once; the list it produces is still linear. The (x:[]) = Nothing line ensures that the list is at least 2 elements long via pattern matching. The result of nextElem 1 [5,3,9,1,6,8] would be Just 6. It works exactly as intended, it's just long, and as you pointed out, \$\endgroup\$ – Carcigenicate Aug 25 '14 at 21:36
  • \$\begingroup\$ the wrapping is only required if the given element is the last on the list. It's wasteful, but otherwise I would have to check if e == last xs. I remember thinking that there was something wrong with that method, but I could have just underthought it. \$\endgroup\$ – Carcigenicate Aug 25 '14 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.