1

这是自定义length函数的经典第一次尝试：

length1    []  = 0
length1 (x:xs) = 1 + length1 xs

这是一个尾递归版本：

length2 = length2' 0 where
    length2' n    []  = n
    length2' n (x:xs) = length2' (n+1) xs

但是，(n+1)不会被严格评估，但是 instad Haskell 会创建一个 thunk，对吗？

这是防止创建 thunk 的正确方法，从而强制对(n+1)?

length3 = length3' 0 where
    length3' n    []  = n
    length3' n (x:xs) = length3' (n+1) $! xs

我将如何使用seq而不是达到相同的效果$!？

4

2 回答 2

4

我认为这不太$!对——第二个参数很严格，所以你只是在强制列表而不是累加器。

您可以使用 seq 获得正确的严格性，如下所示：

let n' = n + 1 in n' `seq` length3' n' xs

我认为更具可读性的版本将使用爆炸模式（GHC 扩展）：

length3' !n (x:xs) = ...
于 2013-07-08T12:30:50.643 回答
4

现在写它的通常方法是：

length3 :: [a] -> Int
length3 = go 0
    where
        go :: Int -> [a] -> Int
        go n []     = n
        go n (x:xs) = n `seq` go (n+1) xs

即，作为累加器中严格列表的折叠。GHC 产生直接转换为 Core：

Main.$wgo :: forall a_abz. GHC.Prim.Int# -> [a_abz] -> GHC.Prim.Int#
Main.$wgo =
  \ (n :: GHC.Prim.Int#) (xs :: [a_abz]) ->
    case xs of
      [] -> n
      _ : xs -> Main.$wgo a (GHC.Prim.+# n 1) xs

表明它在累加器中是未装箱的（因此是严格的）。

于 2013-07-08T12:44:24.940 回答