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)厳密に評価されるわけではありませんが、代わりに Haskell はサンクを作成しますよね?

これは、サンクの作成を防ぎ、厳密な評価を強制する正しい方法(n+1)ですか?

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

seqの代わりに同じ効果を得るにはどうすればよい$!ですか?

4

2 に答える 2

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 に答える