Haskell insert an element on nth position

1
votes

Hi I started to learn haskell but i can't figure out one topic.

Let's say I have a list: [1,2,3] and I'm trying to write a function to insert element on nth position. Any clues how do i do this?

2
haskell

2 Answers

7
votes

You can build an insertAt function like this:

insertAt :: a -> Int -> [a] -> [a]
insertAt newElement 0 as = newElement:as
insertAt newElement i (a:as) = a : insertAt newElement (i - 1) as

One strategy for such problems is to write code for some edge cases and use recursion until an edge case is found.

The mentioned lens package simplifies handling data structures in the sense that the code may become shorter and nicer to write, but at the expense of an additional library to learn.

Both examples highlight that there are several ways to achieve a solution to your problem. I recommend having a look at the Data.List module to gain further insight into typical list operations. The source for the drop function could be a good start for you. Also the provided splitAt function could be a fitting building block for your problem.

As Shersh mentions correctly the above implementation of insertAt is somewhat flawed: It doesn't check for negative positions and in case of one given just continues recursing. This can be particularly bad in case of an infinite list.

We can easily improve the implementation by using guards:

insertAt :: a -> Int -> [a] -> [a]
insertAt newElement _ [] = [newElement]
insertAt newElement i (a:as)
  | i <= 0 = newElement:a:as
  | otherwise = a : insertAt newElement (i - 1) as

This implementation tries to do the right thing by inserting the newElement immediately when in doubt. It is also possible to write a version of insertAt that instead throws errors into our face:

import Data.Monoid ((<>))
import qualified Data.List as List

insertAt :: a -> Int -> [a] -> [a]
insertAt newElement i as
  | null as && i != 0 = error "Cannot insert into empty list other than position 0."
  | null as && i == 0 = [newElement]
  | i >= 0 = let (prefix, suffix) = List.splitAt i
             in prefix <> [i] <> suffix

This version also makes use of List.splitAt for brevity.

1
votes

This should work for positive and negative integers.

insertAt :: [a] -> a -> Int -> [a]
insertAt [] elem pos = [elem]
insertAt (x:xs) elem pos
    | pos == 0 = elem : x : xs
    | pos > 0 = x : insertAt xs elem (pos - 1) 
    | otherwise = x : insertAt xs elem ((pos) + length (x:xs) )