Haskell: Obtaining the Nth element in a Snoc list

Question

I wrote the following function to find the Nth element on a given Snoc list (reverse cons) but I think it's not the most optimal solution to the problem. I was wondering if you would please share some insights, code or advice to see a different solution; one that you might consider does the job more efficiently:

Here's my function:

data ListS a = NilS 
              |Snoc (ListS a) a deriving Show

len :: ListS a -> Int
len NilS       = 0
len (Snoc a b) = 1 + len(a) 

nthElementS :: Int -> ListS a -> a
nthElementS _ NilS = error "Empty List"
nthElementS n s    = if n < 0 || n >= len(s) then error "Invalid Index" 
                     else nthAux ((len(s)-1)-n) s where
                          nthAux 0 (Snoc a b) = b
                          nthAux m (Snoc a b) = nthAux (m-1) a

Some examples:

Main> nthElementS 0 (Snoc (Snoc (Snoc (Snoc (Snoc NilS 1) 2) 3) 4) 5)
1

Main> nthElementS 2 (Snoc (Snoc (Snoc (Snoc (Snoc NilS 1) 2) 3) 4) 5) 
3

As an additional inquiry: What would be the best way to implement a function that concatenates 2 Snoc lists? I am already thinking of a solution but it would require an auxiliary function to keep track of the Nth position, and again, I feel that's not going to make full use of Haskell's advantages over other languages.

Thanks in advance.

your type is isomorphic to the regular cons list. with it your function is actually `nthFromEnd`. Maintaining your list's length together with the list will make it trivial to implement. Otherwise, just take the nth element from the reversed list, or do the equivalent computation with `foldr`, fusing the reversing and the length measuring (not unlike the code in the answer). As for the *O(1)* appending, you could e.g. use [a different data type](https://stackoverflow.com/questions/43941551/explicit-purely-functional-data-structure-for-difference-lists/43945275#43945275) to represent the lists. — Will Ness, Aug 18 '18 at 15:10
Thank you Will Ness, I never thought about applying foldr either. Great suggestions. — Arthur Champs, Aug 18 '18 at 16:18

score 3 · Accepted Answer · answered Aug 18 '18 at 12:20

We can use a "try-and-error" approach where we first try to find that element in the "prefix list", and if that is not sufficient (since the index is larger), we then try the current element. If that still is not enough, it is up to the "parent call" to handle the situation. We can do this by first defining a function with a slightly different output type:

nthShelp :: Int -> ListS a -> Either a Int

So it returns Left x in case it has found the element (x being the element), or Rightn, withn` the "remaining" elements it needs to walk through.

So we can define this with:

nthShelp :: Int -> ListS a -> Either a Int
nthShelp n NilS = Right n
nthShelp n (Snoc hs t) = progress nhs
    where nhs = nthElementS n hs
          progress lx@(Left _) = lx
          progress (Right 0) = Left t
          progress (Right n) = Right (n-1)

So we first call recursively on the head of the list, and then the recursive calls are resolved by decrementing the index until it hits zero, in which case we return the corresponding Left t, and that Left t is than passed back out of the recursive calls.

We can make use of the fact that Either a is a Monad istance, and write this more effective like:

nthShelp :: Int -> ListS a -> Either a Int
nthShelp n NilS = Right n
nthShelp n (Snoc hs t) = nthElementS n hs >>= progress
    where progress 0 = Left t
          progress n = Right (n-1)

Then we can write nthElementS in terms of nthShelp with:

nthElementS :: Int -> ListS a -> a
nthElementS n l | n < 0 = error "Index too small"
                | Left a <- nthShelp n l = a
                | otherwise = error "Index too large"

In terms of time complexity, it is still O(n) (with n the length of the list, not the index we want to obtain). There is no way to do it better with this data structure, since we need to know the number of elements in the prefix, before we know what element to return.

As an additional inquiry: What would be the best way to implement a function that concatenates 2 Cons lists? I am already thinking of a solution but it would require an auxiliary function to keep track of the Nth position, and again, I feel that's not going to make full use of Haskell's advantages over other languages.

Well you can see a concatenation here as replacing the (usally deeply) nested NlS of the second list, by the first list. So if we concatenate concatS l1 NilS, then it is l1, if we concatenate concatS l1 (Snoc NilS x), then it is Snic l1 x). So we can define this recursively as:

concatS :: ListS a -> ListS a -> ListS a
concatS l1 NilS = l1
concatS l1 (Snoc l2 x) = Snoc (concatS l1 l2) x

A disadvantage of the above approach is that it still will work in O(n) if the first list is NilS (so empty). We can add a guard for this, to handle that case:

concatS :: ListS a -> ListS a -> ListS a
concatS NilS = id
concatS l1 = go
    where go NilS = l1
          go (Snoc l2 x) = Snoc (go l2) x

Willem Van Onsem, you are not only generous but extremely clear when it comes to sharing your knowledge. Thank you for your detailed answer and many solutions to this particular problem. I'm currently studying your solutions to understand the thought process more clearly. It's so well explained. Thanks a lot, mate! — Arthur Champs, Aug 18 '18 at 12:55

Haskell: Obtaining the Nth element in a Snoc list

1 Answers1