Почему более общий тип влияет на время выполнения в Haskell?

Рассмотрим две следующие реализации бесконечной последовательности Фибоначчи:

fibsA :: Num a => [a]
fibsA = 0:1:(zipWith (+) fibsA (tail fibsA))

fibsB :: [Integer]
fibsB = 0:1:(zipWith (+) fibsB (tail fibsB))

В GHCI выполнение fibsB !! k выполняется намного быстрее, чем выполнение fibsA !! k. В частности, кажется, что значения fibsA непрерывно пересчитываются (не сохраняются или сохраняются).

Кроме того, когда сигнатура типа опущена, GHCI :t показывает, что она [Integer], и функция выполняет соответственно.

Это также происходит в скомпилированном коде (ghc -O3 Fibs.hs).

Почему это так, что Integer намного быстрее, чем Num a => a?

Ответ 1

Когда вы пишете fibsA :: Num a => [a], компилятор строит то, что по существу

fibsA :: NumDict a -> [a]

Где

data NumDict a = NumDict
    { (+)         :: a -> a -> a
    , (-)         :: a -> a -> a
    , (*)         :: a -> a -> a
    , negate      :: a -> a
    , abs         :: a -> a
    , signum      :: a -> a
    , fromInteger :: Integer -> a
    }

Обратите внимание, что Num a переместился из ограничения на аргумент функции. Класс типов - это просто таблица поиска для каждого типа, реализующего класс. Итак, для Num, по умолчанию вы бы указали

mkInteger_NumDict :: NumDict Integer
mkInteger_NumDict = NumDict
    { (+) = integer_plus
    , (-) = integer_minus
    , (*) = integer_mult
    , ...
    }

mkInt_NumDict     :: NumDict Int

mkFloat_NumDict   :: NumDict Float

mkDouble_NumDict  :: NumDict Double

и они автоматически передаются функции с использованием класса типов при разрешении экземпляра. Это означает, что наша функция fibsA по существу принимает аргумент. Когда вы вызываете его из GHCi, правила по умолчанию нажимают и выбирают Integer, но поскольку он называется таким образом, он будет выглядеть больше как внутри:

{-# RecordWildCards #-}  -- To reduce typing

fibsA :: NumDict a -> [a]
fibsA [email protected](NumDict{..}) = fromInteger 0 : fromInteger 1 : zipWith (+) (fibsA nd) (tail $ fibsA nd)

Вы видите проблему с этим? Он по-прежнему рекурсивный, но теперь он должен сделать вызов функции на каждом шаге, снижая производительность. Если вы хотите сделать это очень быстро, умный программист сделает

fibsA [email protected](NumDict{..}) = fromInteger 0 : fromInteger 1 : zipWith (+) fibsA' (tail fibsA')
    where fibsA' = fibsA nd

Это, по крайней мере, позволяет memoization. Однако двоичный файл haskell не может выполнять эту оптимизацию во время выполнения, что происходит во время компиляции. Итак, в конечном итоге вы получаете более медленную рекурсивную функцию. С fibsB вы указываете тип конкретно, нет никаких полиморфных ограничений на его подпись типа. Значение fibsB не имеет неявных или явных аргументов, поэтому при упоминании его указатель на тот же объект в памяти. fibsA - это указатель на функцию, поэтому при использовании рекурсивно он возвращает новые объекты в памяти и не имеет memoization. Вот почему fibsB быстрее, чем fibsA, оптимизируется только fibsB, потому что компилятор не должен заставить его работать для всех Num, только Integer.

Ответ 2

В дополнение к подробному объяснению @bheklilr: вы также можете быстро сделать fibsA, если вы выполняете разделение списка внутри функции, делая ее нерекурсивной (скрывая рекурсию внутри):

fibsA' :: Num a => [a]
fibsA' = 
  let f = 0:1:(zipWith (+) f (tail f))
  in f