Is there an indexed list in Haskell and is it good or bad?

Question

I am a new comer to the Haskell world and I am wondering if there is something like this:

data IndexedList a = IList Int [a]

findIndex::(Int->Int)->IndexedList a->(a,IndexedList a)
findIndex f (IList x l) = (l!!(f x), IList (f x) l)

next::IndexedList a->(a,IndexedList a)
next x = findIndex (+1) x

I've noticed that this kind of list is not purely functional but kind of useful for some applications. Should it be considered harmful?

Thanks,

Bob

Answer 1

It's certainly useful to have a list that comes equipped with a pointed to a particular location in the list. However, the way it's usually done in Haskell is somewhat different - rather than using an explicit pointer, we tend to use a zipper.

The list zipper looks like this

data ListZipper a = LZ [a] a [a] deriving (Show)

You should think of the middle field a as being the element that is currently pointed to, the first field [a] as being the elements before the current position, and the final field [a] as being the elements after the current position.

Usually we store the elements before the current one in reverse order, for efficiency, so that the list [0, 1, 2, *3*, 4, 5, 6] with a pointer to the middle element, would be stored as

LZ [2,1,0] 3 [4,5,6]

You can define functions that move the pointer to the left or right

left  (LZ (a:as) b bs) = LZ as a (b:bs)
right (LZ as a (b:bs)) = LZ (a:as) b bs

If you want to move to the left or right n times, then you can do that with the help of a function that takes another function, and applies it n times to its argument

times n f = (!!n) . iterate f

so that to move left three times, you could use

>> let lz = LZ [2,1,0] 3 [4,5,6]
>> (3 `times` left) lz
LZ [] 0 [1,2,3,4,5,6]

Your two functions findIndex and next can be written as

next :: ListZipper a -> (a, ListZipper a)
next = findIndex 1

findIndex :: Int -> ListZipper a -> (a, ListZipper a)
findIndex n x = let y@(LZ _ a _) = (n `times` right) x in (a, y)

Answer 2

Contrary to what you think this list is in fact purely functional. The reason is that IList (f x) l creates a new list (and does not, as you may think, modify the current IndexedList). It is in general not that easy to create non-purely functional data structures or functions in Haskell, as long as you stay away from unsafePerformIO.

The reason I would recommend against using the IndexedList is that there is no assurance that the index is less than the length of the list. In this case the lookup l!!(f x) will fail with an exception, which is generally considered bad style in Haskell. An alternative could be to use a safe lookup, which returns a Maybe a like the following:

findIndex :: (Int -> Int) -> IndexedList a -> (Maybe a, IndexedList a)
findIndex f (IList i l) = (maybe_x, IList new_i l)
    where
        new_i   = f i
        maybe_x = if new_i < length l 
                  then Just (l !! newI) 
                  else Nothing

I can also not think of a usecase where such a list would be useful, but I guess I am limited by my creativity ;)