# Implementing insertAt for both [a] and [(i,a)] lists

I've implemented generic insertAt function which inserts element into both indexed and ordinary lists. Here are some examples:

-- ordinary list
insertAt 1 5 [1, 2]         == [1, 5, 2]
-- indexed list
insertAt 1 5 [(0,1), (1,2)] == [(0,1), (1, 5), (2, 2)]


Here is the code:

{-# LANGUAGE TypeFamilies, FlexibleInstances #-}

import Data.List
import Data.Ord

-- Determines index type of list
type family I i a where
I i (j, e) = j -- index of [(j, e)] is j
I i e      = i -- index of [e], is i

-- Determines element type of list
type family E a where
E (j, e) = e -- element of [(j, e)] is e
E e      = e -- element of [e] is e

-- Class of element of list
class ListElem e where
insertAt ::
( e ~ (i, a, b) -- e is a tuple where
, i ~ I i b     -- i is index
, a ~ E b       -- a is element
) => i -> a -> [b] -> [b]

enumerate :: (Num i, Enum i) => [a] -> [(i, a)]
enumerate = zip [0..]

-- Instance for non indexed lists
instance Integral i => ListElem (i, e, e) where
insertAt i x = map snd . insertBy (comparing fst) (i, x) . enumerate

-- Instance for indexed lists
instance Integral i => ListElem (i, e, (i, e)) where
insertAt i x xs = let (l, r) = genericSplitAt i xs in
l ++ (i, x) : map (\ (j, y) -> (j + 1, y)) r


Only problem I have is that type of i in instance for ordinary lists cannot be automaticaly inferred. So, I should put type annotations everywhere I use it. Instance for indexed lists works fine.

• Any simple examples of usage? – Artem Pelenitsyn Nov 26 '15 at 12:20