Строгая оценка целочисленного аккумулятора

Question

Вот классическая первая попытка на заказ 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 вместо $!?

Answer 1

Обычный способ написать это будет так:

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

Показывает, что он не распакован (и, следовательно, строг) в аккумуляторе.

Answer 2

Я не думаю, что это правильно$! строг в своем втором аргументе, так что вы просто форсируете список, а не аккумулятор.

Вы можете получить правильную строгость, используя seq что-то вроде этого:

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

Я думаю, что более читаемая версия будет использовать шаблоны взрыва (расширение GHC):

length3' !n (x:xs) = ...