Haskell 继续传递列表中元素的样式索引

Question

我正在尝试做一系列的例子来练习 Haskell。我目前正在学习继续传递，但我对如何实现像 find index of element in list 这样的函数有点困惑：

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

像阶乘这样的例子是有意义的，因为除了乘法之外实际上没有对数据进行任何处理，但在索引函数的情况下，我需要将我正在查看的元素与我正在查看的元素进行比较我正在寻找，但我似乎无法弄清楚如何使用函数参数来做到这一点。

任何帮助都会很棒。

Answer 1

首先让我向您展示一个可能的实现方式：

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)

如果你喜欢无点风格：

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))

工作原理

技巧是使用 continuations 来计数索引 - 那些延续将获得 右侧的索引 并增加它。

如您所见，如果找不到元素，这将导致错误。

示例：

λ> 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

我是怎么想出来的

解决此类问题的一个好方法是首先写下带有延续的递归调用：

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

现在您必须考虑您希望 valFromXs 成为什么（作为类型和作为值）- 但请记住您的典型 start（如这里）会做第一个continuationid，所以type只能是Int -> Int。所以应该清楚我们在这里谈论的是索引转换。由于 useCont 在下一次调用中只会知道尾部 xs，因此很自然地将此索引视为 相对于 xs 并且从这里开始休息应该很快。

IMO 这只是

的另一个实例

Let the types guide you Luke

;)

备注

我认为这不是 Haskell 中 continuations 的典型用法。

一次你也可以为此使用一个累加器参数（概念上更简单）：

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)

或者 (see List.elemIndex) 你可以使用 Haskells laziness/list-comprehensions 让它看起来更好:

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

Answer 2

如果您有一个值 a，那么要将其转换为 CPS 样式，对于某些未指定的 r，您可以将其替换为类似 (a -> r) -> r 的内容。在您的情况下，基本函数是 index :: Eq a => a -> [a] -> Maybe Int，因此 CPS 形式是

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

甚至

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

让我们实现后者。

index x as success failure =

值得注意的是，有两种延续，一种是成功的结果，一种是失败的结果。我们将在必要时应用它们，并像往常一样引入列表的结构。首先，很明显，如果 as 列表为空，那么这是一个失败

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

在成功案例中，我们通常对是否 x == a 感兴趣。当它为真时，我们将索引 0 传递给成功延续，因为毕竟我们在输入列表的第 0 个索引处找到了匹配项。

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

那么当我们还没有匹配时会发生什么？如果我们要以不变的方式传递成功延续，那么假设找到匹配项，最终将以 0 作为参数调用它。但是，这会丢失有关我们已经尝试调用它一次这一事实的信息。我们可以通过修改 continuation

来纠正这个问题

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

另一种思考方式是我们在延续中有收集 "post" 操作，因为最终计算结果将通过该代码

-- 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

如果我们用 pointfree 风格写递归分支，这可能会更清楚

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

它显示了我们如何修改延续以在每个递归调用中包含一个增量。加在一起的代码是

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

Haskell 继续传递列表中元素的样式索引

Haskell Continuation passing style index of element in list

haskell

functional-programming

continuation-passing

工作原理

示例：

我是怎么想出来的

备注