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

Question

我正在努力练习Haskell的一系列例子.我目前正在学习继续传递,但是我对如何实现像list中的元素的查找索引这样的函数有点困惑:

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

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

任何帮助都会很棒.

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这只是另一个例子

让这些类型指导你卢克

;)

备注

我不认为这是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)

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

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