如何在Haskell中找到'无限'可折叠结构的第k个元素？

问题描述：

我想定义上Foldable类型如何在Haskell中找到'无限'可折叠结构的第k个元素？

safeIndex :: (Foldable t, Integral i) => t a -> i -> Maybe a 
safeIndex = foldr step (const Nothing) 
    where 
    step :: Integral i => a -> (i -> Maybe a) -> i -> Maybe a 
    step x f i = if i == 0 
       then Just x 
       else f (i - 1)

功能，safeIndex的作品，但它并不适用于无限列表工作。要使foldr在中间停下来，我认为我们必须确定它是否应该仅以step的第一个参数停止，这似乎是不可能的。

是否有可能修复该函数以使其在无限结构上工作？如果不是，我们应该限制t的类型类别？

你为什么在这里使用'forall'？ –

否则'step'的显式类型签名将无法编译。我启用了'ScopedTypeVariable'语言扩展:) –

'safeIndex [1 ..] 3'输出'只是4'。然而，它不适用于无限的snoc列表，但对于那些“从正确的索引”摆在首位的用户来说是没有意义的。 –

答

其实问题描述中的定义已经适用于无限内置列表。这是一些其他的错误，让我觉得它不能;）（见评论。）

答

如果您不介意承担依赖项，Gabriel Gonzalez的foldl library提供index和genericIndex折叠符合您的目的。

例如，你可以写

safeIndex :: (Foldable f, Integral a) => a -> f b -> Maybe b 
safeIndex = fold . genericIndex

除此之外，您发布的代码似乎做你想要什么。

编辑：我隔开了“无限列表”位。

这将适用于无限列表，但我不知道有一个明智的方法来定义它的所有Foldable s。

safeIndex' :: Int -> [a] -> Maybe a 
safeIndex' n = listToMaybe . foldr (.) id (replicate n (drop 1))

编辑2：

从头开始，你在原来的职位已经得到了应该用于任何Foldable工作。

谢谢！这是一个方便的图书馆，但它不适用于无限列表。 –

噢，我，你说得对。我完全了解了关于无限列表的一点。我会用一个更丑陋的想法编辑。 –

如何在Haskell中找到'无限'可折叠结构的第k个元素？

相关推荐