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

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

这个怎么运作

把戏是使用延续来计算索引 - 这些延续将使索引向右并增加它。

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

例子:

λ> 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成为(作为一个类型和一个值)——但请记住你的典型 开始 (如这里)将进行第一个延续 id ，所以类型只能是 Int -> Int .所以应该清楚，我们在这里谈论的是索引转换。如 useCont只会知道尾部 xs在下一次调用中，很自然地看到该索引为 相对于 xs 从这里开始，其余的应该很快跟进。

IMO 这只是另一个例子

Let the types guide you Luke

;)

评论

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

这一次，您可以使用 蓄能器对此的论点(概念上更简单):

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 ) 你可以使用 Haskell 懒惰/列表理解来让它看起来更好:

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