Почему `data` вызывает бесконечный цикл, а newtype нет - PullRequest
Новая
       76

Почему `data` вызывает бесконечный цикл, а newtype нет

9 голосов
/ 01 апреля 2019

Я учусь Arrow, следуя инструкции программирование со стрелками .Я набрал следующий код в соответствии со статьей, за исключением того, что SF определяется data, а не newtype, как в статье (на самом деле , я сделал это изменение случайно, так как набралкод из памяти ): 

import Control.Category
import Control.Arrow
import Prelude hiding (id, (.))

data SF a b = SF { runSF :: [a] -> [b] }  -- this is the change, using data instead of newtype as in the paper 

-- The folowing code is the same as in the paper
instance Category SF where
  id = SF $ \x -> x
  (SF f) . (SF g) = SF $ \x -> f (g x)

instance Arrow SF where
  arr f = SF $ map f
  first (SF f) = SF $ unzip >>> first f >>> uncurry zip

instance ArrowChoice SF where
  left (SF f) = SF $ \xs -> combine xs (f [y | Left y <- xs])
    where
      combine (Left _ : ys) (z:zs) = Left z : combine ys zs
      combine (Right y : ys) zs = Right y : combine ys zs
      combine [] _ = []

delay :: a -> SF a a
delay x = SF $ init . (x:)

mapA :: ArrowChoice a => a b c -> a [b] [c]
mapA f = arr listcase >>>
         arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))

listcase :: [a] -> Either () (a, [a])
listcase [] = Left ()
listcase (x:xs) = Right (x, xs)

Когда я загружаю файл в ghci и выполняю runSF (mapA (delay 0)) [[1,2,3],[4,5,6]], он запускает бесконечный цикл и, наконец, исчерпывает память.Если я изменю data обратно на newtype, все в порядке.Та же проблема возникает в ghc 8.0.2, 8.2.2 и 8.6.3.

Та же проблема существует, даже когда я компилирую код в исполняемый файл.

Я думал, что разница между data и newtype, когда определяю структуру данных только с одним полем,стоимость выполнения.Но эта проблема, кажется, подразумевает большую разницу между ними.Или может быть что-то, чего я не заметил в классе типов Arrow.

Может быть, у кого-нибудь есть идеи?Большое спасибо!

1 Ответ

12 голосов
/ 01 апреля 2019

Давайте посмотрим на этот пример. 

data A = A [Int]
    deriving (Show)

cons :: Int -> A -> A
cons x (A xs) = A (x:xs)

ones :: A
ones = cons 1 ones

Мы ожидаем, что ones должно быть A [1,1,1,1...], потому что все, что мы сделали, это обернули список в конструкторе data.Но мы были бы неправы.Напомним, что сопоставления с образцами являются строгими для data конструкторов.То есть cons 1 undefined = undefined, а не A (1 : undefined).Поэтому, когда мы пытаемся оценить совпадения с шаблоном ones, cons по второму аргументу, что заставляет нас оценивать ones ... у нас возникает проблема.

newtype s не делаютэтот.Во время выполнения newtype конструкторы невидимы, так что, как если бы мы написали эквивалентную программу в простых списках 

cons :: Int -> [Int] -> [Int]
cons x ys = x:ys

ones = cons 1 ones

, которая является совершенно производительной, поскольку при попытке оценить ones возникает : конструктор между нами и следующая оценка ones.

Вы можете вернуть семантику newtype, сделав ваш шаблон конструктора данных совпадающим с ленивым: 

cons x ~(A xs) = A (x:xs)

Этопроблема с вашим кодом (я столкнулся с этой проблемой, делая именно эту вещь).Есть несколько причин, по которым data соответствие шаблонов строго по умолчанию;самое убедительное, что я вижу, это то, что сопоставление с образцом в противном случае было бы невозможно, если бы у типа было более одного конструктора.Существует также небольшая накладная нагрузка времени на сопоставление с ленивым шаблоном, чтобы исправить некоторые незначительные утечки GC;подробности, связанные в комментариях.

...