Haskell insertAt solutions

Question

I was working on Haskell Problem 21:

Insert an element at a given position into a list.

Example:

* (insert-at 'alfa '(a b c d) 2)
(A ALFA B C D)

I have two different solutions:

--Problem 21 (also not tail recursive)
insertAt :: a -> [a] -> Int -> [a]
insertAt v [] n = [v]
insertAt v arr 1 = (v:arr)
insertAt v (x:xs) n = (x:(insertAt v xs $ n - 1))

--Tail recursive version
insertAtB :: a -> [a] -> Int -> [a]
insertAtB v arr n = loop v n arr []
    where loop v n [] acc = (myReverse acc) ++ [v]
          loop v 1 arr acc = (myReverse acc) ++ [v] ++ arr
          loop v n (x:xs) acc = loop v (n - 1) xs (x:acc)

Which is better stylistically? Which is better in terms of runtime and memory use?

How can you determine what order of arguments is the best for currying? Is it only based on your own usage or is there a better way to determine this?

Answer 1

The first solution is infinitely better than the second solution. In Haskell, tail recursion is not the main concern. Rather, the primary consideration is laziness. Furthermore, operations like list reversal (myReverse, which you haven't shown us) and list concatenation (the ++ operator) should be avoided wherever possible, since they involve traversing an entire list to its end. Considering that lists in Haskell may be infinitely long, you could be inviting trouble.

I consider your insertAt v [] n = [v] case to be superfluous and harmful. If you are inserting an element into an empty array, I think it's fair to require the index to be 1. I would write it like this:

insertAt :: a -> [a] -> Int -> [a]
insertAt v xs     1 = v : xs
insertAt v (x:xs) n = x : (insertAt v xs (n - 1))

---

In my opinion, the interface specified in the challenge is weird: the function would be better named insertBefore, since I expect that inserting an element at position 0 would place it at the head of the resulting list.

As a rule of thumb, Haskell functions should be designed so that the parameters are ordered starting from the one that is least likely to vary. I would certainly not place the index at the end. One better design would be insertAt value index list, such that insertAt value index could be treated as a partial function to be applied to some list. Another reasonable design would be insertAt list index value, such that insertAt list index could be treated as a partial function that is waiting to fill a specified hole in the list. However, with the current specification, the partial function insertAt value list means "add value to list, but we don't know where yet", which seems like a rare use case to me.