Push List Element to Top

Question

Please evaluate this function. It takes a list [a] and an Int, i.e. the index, and returns a new list with the selected item at the top of the list. Note that it returns Maybe [a] to account for bad indexes.

pushToTop :: [a] -> Int -> Maybe [a]
pushToTop [] _ = Just []
pushToTop xs i 
 | i >= length xs || i < 0 = Nothing
 | i == 0 = Just xs
 | otherwise = Just $ newTop : rest
 where zipped = zip [0..] xs
 newTop = xs !! i
 rest = (map (\x -> snd x) . filter (\x -> fst x /= i)) zipped

I'm also curious if my usage of !! is OK given the 2 guards on i.

Answer 1

Yes, the guards make !! safe, but your code has other issues, stylistic and functional:

Unneeded pointful style

First, it's often a good idea to try running your code through HLint. Doing so, you get the following suggestion:

pushToTop.hs:9:52: Error: Avoid lambda
Found: \x -> snd x
Why not: snd
1 suggestion

Indeed, why not. If we're to use point-free style for this, we could also simplify

filter (\x -> fst x /= i)

to

filter ((/= i) . fst)

At some point, point-free style can get difficult to read, but in this case I think it is still readable.

Parentheses that can be replaced with a use of $

Right here:

(map (\x -> snd x) . filter (\x -> fst x /= i)) zipped

Using $, you could also inline zipped non-awkwardly:

map snd . filter ((/= i) . fst) $ zip [1..] xs

Incorrect base case

Shouldn't any index on an empty list be considered an error? As is, you're completely ignoring the index. For consistency, I would make the first case return Nothing.

Unnecessary case

This case is already handled by the latter case:

 | i == 0 = Just xs

It can be safely removed.

Failure to work on infinite lists

The operation you have defined (move an element at a certain index to the front) is well-defined on infinite lists, but your code fails to handle the case. In particular, length will not terminate on infinite lists. The current structure of your code cannot handle this. Rewriting it to make explicit the recursion and to avoid calculating the length should make it work on infinite lists.

Test case:

ghci> fmap (take 20) $ pushToTop [0..] 12
[12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19]

Answer 2

There are some operations in Haskell that kill laziness. In particular, length and ++ should raise red flags, and here you used length.

In addition, !! should be avoided, as indexing into a list is not an O(1) operation. (Arrays and vectors support O(1) indexing.)

For those reasons, your current strategy, which is to

1. check for validity
2. pluck out the element to be the "top"
3. construct a list of the remainder

... is eager and/or inefficient at all three steps.

In summary, you should consider a recursive approach. Don't try to construct "the" answer. Instead, think about how to reduce the given inputs to a slightly smaller problem.

import Data.Maybe
pushToTop :: [a] -> Int -> Maybe [a]
pushToTop [] _ = Nothing
pushToTop xs 0 = Just xs
pushToTop (x:xs) i 
 | i < 0 = Nothing
 | isNothing ptt' = Nothing -- Propagate index-too-large error
 | otherwise = let (top:xs') = fromJust ptt' in Just (top:x:xs')
 where ptt' = pushToTop xs (i - 1)

• Sjoerd Job Postmus: I wonder if the propagation of Nothing is as efficient as one might hope. Also, I think the packing/unpacking of the Just might be a bit inefficient.

Answer 3

First of all, I noticed that pushToTop [] -1 is valid, but pushToTop [0] -1 is not. I would recommend also checking the bounds in the first case. This can be done by dropping the first special case. On the other hand, the downside is that it never makes sense to call pushToTop with an empty list, as no argument would be valid. I think that's ok, because the concept doesn't make sense in this case.

How you determine newTop and rest is quite clear, but I would propose using splitAt from Data.List for this.

pushToTop :: [a] -> Int -> Maybe [a]
pushToTop xs i
 | i < 0 = Nothing
 | otherwise = case splitAt i xs of
 (rest_init, newTop : rest_tail) -> Just $ newTop : rest_init ++ rest_tail
 _ -> Nothing

If you do want to have pushToTop [] n work, my own suggestion would be to replace 'Nothing' with 'Just xs' in the above statement, so that the handling of index-out-of-bounds is consistent between pushToTop [] -1 and pushToTop [0] -1.

• 200_success: length xs will break when given an infinite list, and ++ is probably suboptimal for large i.