Haskell Continuation passing style index of element in list

Question

There's a series of examples I'm trying to do to practice Haskell. I'm currently learning about continuation passing, but I'm a bit confused as to how to implement a function like find index of element in list that works like this:

index 3 [1,2,3] id = 2

Examples like factorial made sense since there wasn't really any processing of the data other than multiplication, but in the case of the index function, I need to compare the element I'm looking at with the element I'm looking for, and I just can't seem to figure out how to do that with the function parameter.

Any help would be great.

Answer 1

first let me show you a possible implementation:

index :: Eq a => a -> [a] -> (Int -> Int) -> Int
index _ [] _  = error "not found"
index x (x':xs) cont
  | x == x'   = cont 0
  | otherwise = index x xs (\ind -> cont $ ind + 1)

if you prefer point-free style:

index :: Eq a => a -> [a] -> (Int -> Int) -> Int
index _ [] _  = error "not found"
index x (x':xs) cont
  | x == x'   = cont 0
  | otherwise = index x xs (cont . (+1))

how it works

The trick is to use the continuations to count up the indices - those continuations will get the index to the right and just increment it.

As you see this will cause an error if it cannot find the element.

examples:

λ> index 1 [1,2,3] id
0
λ> index 2 [1,2,3] id
1
λ> index 3 [1,2,3] id
2
λ> index 4 [1,2,3] id
*** Exception: not found

how I figured it out

A good way to figure out stuff like this is by first writing down the recursive call with the continuation:

useCont a (x:xs) cont = useCont a xs (\valFromXs -> cont $ ??)

And now you have to think about what you want valFromXs to be (as a type and as a value) - but remember your typical start (as here) will be to make the first continuation id, so the type can only be Int -> Int. So it should be clear that we are talking about of index-transformation here. As useCont will only know about the tail xs in the next call it seems natural to see this index as relative to xs and from here the rest should follow rather quickly.

IMO this is just another instance of

Let the types guide you Luke

;)

remarks

I don't think that this is a typical use of continuations in Haskell.

For once you can use an accumulator argument for this as well (which is conceptional simpler):

index :: Eq a => a -> [a] -> Int -> Int
index _ [] _  = error "not found"
index x (x':xs) ind
  | x == x'    = ind
  | otherwise = index x xs (ind+1)

or (see List.elemIndex) you can use Haskells laziness/list-comprehensions to make it look even nicer:

index :: Eq a => a -> [a] -> Int
index x xs = head [ i | (x',i) <- zip xs [0..], x'== x ]