Haskell向量模式匹配

Question

Haskell向量模式匹配

6

有可能在向量上使用列表样式模式匹配吗？

例如：

import qualified Data.Vector as V

f :: V.Vector a -> a
f (x:xs) = x

出现错误

- matt

3个回答

5

@Cactus指出，-XPatternSynonym（在7.8中引入）结合-XViewPattern可以用于对向量进行模式匹配。我在此基础上进一步扩展他的评论。

pattern Empty <- (V.null -> True)

上面定义了一个模式同义词 Empty，用于表示空向量。 Empty 模式使用视图模式 (V.null -> True) 匹配空向量。然而，它不能在其他地方用作表达式，即它是一个单向同义词，因为系统不知道 Empty 是一个向量 (我们只知道 null v 是 True，但还可能有其他向量也会返回 True)。

为了解决这个问题，可以添加一个 where 子句，指定 Empty 实际上是一个空向量，即它是一个双向同义词，同时还需要一个类型签名。

pattern Empty :: Vector a
pattern Empty <- (V.null -> True) where Empty = V.empty

使用这个模式同义词可以定义uncons而不需要if表达式：

uncons :: Vector a -> Maybe (a, Vector a)
uncons Empty = Nothing
uncons v     = Just (unsafeHead v, unsafeTail v)

我们使用uncons来定义单向同义词。注意，我没有将其设为双向的，因为对于向量来说cons的成本很高：

pattern (:<|)  :: a -> Vector a -> Vector a
pattern x :<| xs <- (uncons -> Just (x, xs))

无论如何，我们现在终于能够像对待列表一样对待向量进行模式匹配了：

vsum :: Num a => Vector a -> a 
vsum Empty = 0
vsum (x :<| xs) = x + vsum xs

完整的代码在这里。

- L.-T. Chen

1

向量不适用于那种模式匹配 - 它们被创建为给予 Haskell O(1) 列表，或者可以从任何点有效地访问的列表。

与您编写的最接近的东西可能是这样的：

f v = V.head v

如果你需要递归，tail 函数可以获取列表的其余部分。

但是，如果你想要像那样沿着列表移动做某些事情，就有向量等价函数，例如 foldl、find、map 等。这取决于你的意图。

- Wolfe Macfarlane

我正在尝试在向量上运行函数 f :: Vector a -> a，但我想要在每添加一个新项时移动到向量的下一个位置并重新计算（同时保留其他值）。例如，在 [1,2,3,4,5,6,7,8,10] 上，我想要 [f [1], f [1,2], f [1,2,3]..] 等等。 - matt

@matthias 那是一个扫描。 - rampion

@rampion 对不起，我有点困惑。扫描不是一种累积函数，将结果传递给下一次迭代吗？我该如何为上面的内容编写扫描函数？感谢您的帮助。 - matt

这取决于 f 的定义。如果存在 g，使得对于所有的 i，都有 f [a_0...a_i] = g (f [a_0...a_{i-1}]) a_i，并且存在 b 使得 f [] = b，那么 scanl g b [a_0 .. a_n] 将产生 [ f [], f [a_0], f [a_0,a_1], f [a_0, a_1, a_2] ..., f [a_0, a_1, ... a_n ] ]。这样的实现通常更有效率，因为它们只需要做 O(n) 的工作，而不是 O(n^2)。 - rampion

如果不是这样，那么你需要的是 Data.Vector 版本的 inits，使用 init 实现起来并不难。inits [ a_0, a_1 ... a_n ] = [ [], [a_0], [a_0, a_1], [a_0, a_1, a_2], ..., [a_0, a_1, ..., a_n] ]，所以你可以使用 fmap f . inits。 - rampion

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rampion · Accepted Answer

-XViewPatterns 可以让您做到这一点：

{-# LANGUAGE ViewPatterns #-}
module VecViewPats where

import Data.Vector (Vector)
import qualified Data.Vector as V

uncons :: Vector a -> Maybe (a, Vector a)
uncons v = if V.null v
  then Nothing
  else Just (V.unsafeHead v, V.unsafeTail v)

vsum :: Num a => Vector a -> a
vsum (uncons -> Just (a,av)) = a + vsum av
vsum (uncons -> Nothing) = 0

或者 -XLambdaCase

import Control.Category ((>>>))
-- ...
vsum :: Num a => Vector a -> a
vsum = uncons >>> \case
  Just (a,av) -> a + vsum av
  Nothing     -> 0

但说实话，这似乎有点像代码异味，因为你使用一个数据结构（Vector）作为另一个（[]），这表明你选择的数据结构可能不太合适。

如果你真的只是想在某个算法中将其视为列表，为什么不使用toList呢？