0
\$\begingroup\$

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?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I would use built-ins insertAt item xs n = take n xs ++ [item] ++ drop n xs \$\endgroup\$ Commented Oct 31, 2016 at 20:12
  • \$\begingroup\$ splitAt would get both in one pass. \$\endgroup\$ Commented Nov 5, 2016 at 11:33

1 Answer 1

Reset to default
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I added the insertAt v [] n case to handle indices that are way out of bounds (where v would just be added at the end). Would throwing an error be better in that case? \$\endgroup\$ Commented Nov 1, 2016 at 0:55
  • \$\begingroup\$ I would just omit that case and let it fail. \$\endgroup\$ Commented Nov 1, 2016 at 0:56

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.