4
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.