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.

Tartary

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 ]

Radman

I'd rather use the type signature index :: Eq a => a -> [a] -> (Int -> r) -> r. By keeping the result type of the continuation unspecified, you have less freedom to make mistakes while letting the types guide you. – Nairn

@Nairn true, maybe I assumed the Int to early ;) - you think it would be clearer if I rewrite it? – Radman

Answer 2

If you have a value a then to convert it to CPS style you replace it with something like (a -> r) -> r for some unspecified r. In your case, the base function is index :: Eq a => a -> [a] -> Maybe Int and so the CPS form is

index :: Eq a => a -> [a] -> (Maybe Int -> r) -> r

or even

index :: Eq a => a -> [a] -> (Int -> r) -> r -> r

Let's implement the latter.

index x as success failure =

Notably, there are two continuations, one for the successful result and one for a failing one. We'll apply them as necessary and induct on the structure of the list just like usual. First, clearly, if the as list is empty then this is a failure

  case as of
    []      -> failure
    (a:as') -> ...

In the success case, we're, as normal, interested in whether x == a. When it is true we pass the success continuation the index 0, since, after all, we found a match at the 0th index of our input list.

  case as of
    ...
    (a:as') | x == a    -> success 0
            | otherwise -> ...

So what happens when we don't yet have a match? If we were to pass the success continuation in unchanged then it would, assuming a match is found, eventually be called with 0 as an argument. This loses information about the fact that we've attempted to call it once already, though. We can rectify that by modifying the continuation

  case as of
    ...
    (a:as') ...
            | otherwise -> index x as' (fun idx -> success (idx + 1)) failure

Another way to think about it is that we have the collect "post" actions in the continuation since ultimately the result of the computation will pass through that code

-- looking for the value 5, we begin by recursing
1 :
    2 :
        3 :
            4 :
                5 : _ -- match at index 0; push it through the continuation
                0     -- lines from here down live in the continuation
            +1
        +1
    +1
+1

This might be even more clear if we write the recursive branch in pointfree style

            | otherwise -> index x as' (success . (+1)) failure

which shows how we're modifying the continuation to include one more increment for each recursive call. All together the code is

index :: Eq a => a -> [a] -> (Int -> r) -> r -> r
index x as success failure
  case as of
    [] -> failure
    (a:as') | x == a    -> success 0
            | otherwise -> index x as' (success . (+1)) failure

Cheung

As a one-liner: index x xs s f = foldr (\x' r i -> if x == x' then s i else r (succ i)) (const f) xs 0 – Gombach