Как сделать CAF не CAF в Haskell?

Как создать постоянную аппликативную форму, а не постоянную аппликативную форму, чтобы остановить ее сохранение на протяжении всей жизни программы?

Я пробовал этот подход:

-- | Dummy parameter to avoid creating a CAF twoTrues :: () -> [[[Bool]]] twoTrues _ = map (++ (True : repeat False)) . trueBlock  [1..] 

но он, похоже, не работает – профиль показывает, что он все еще сохраняется и по- прежнему отмечает его как CAF.

Я нашел один соответствующий результат Google по этому поводу , ответ Саймона Пейтона-Джонса на Нила Митчелла, который задал именно этот вопрос, но этот ответ относится к мертвой ссылке, к сожалению.

    Полный пример

    Вот небольшой пример, который показывает ситуацию:

     module A where big :: () -> [Int] big _ = [1..10^7] 

    Похож на функцию, верно? Но что делает GHC? Он перемещает перечисление на верхний уровень!

     A.big1 :: [Int] [ Unf=Unf{Src=, TopLvl=True, Arity=0, Value=False, ConLike=False, Cheap=False, Expandable=False, Guidance=IF_ARGS [] 7 0}] A.big1 = case A.$wf1 10 A.big2 of ww_sDD { __DEFAULT -> eftInt 1 ww_sDD } A.big :: () -> [Int] [Arity=1, Unf=Unf{Src=InlineStable, TopLvl=True, Arity=1, Value=True, ConLike=True, Cheap=True, Expandable=True, Guidance=ALWAYS_IF(unsat_ok=True,boring_ok=True) Tmpl= \ _ -> A.big1}] A.big = \ _ -> A.big1 

    По электронной почте Ой!


    Так что мы можем сделать?

    Отключить оптимизацию

    Это работает, но не желательно:

     A.big :: () -> [Int] [GblId, Arity=1] A.big = \ _ -> enumFromTo @ Int $fEnumInt (I# 1) (^ @ Int @ Type.Integer $fNumInt $fIntegralInteger (I# 10) (smallInteger 7)) 

    Не встроенный, и больше функций

    Сделайте все в функции, в том числе enumFromTo , enumFromTo параметр для рабочих:

     big :: () -> [Int] big u = myEnumFromTo u 1 (10^7) {-# NOINLINE big #-} myEnumFromTo :: () -> Int -> Int -> [Int] myEnumFromTo _ nm = enumFromTo nm {-# NOINLINE myEnumFromTo #-} 

    Теперь мы, наконец, CAF-free! Даже с -O2

     A.myEnumFromTo [InlPrag=NOINLINE] :: () -> Int -> Int -> [Int] A.myEnumFromTo = \ _ (n_afx :: Int) (m_afy :: Int) -> $fEnumInt_$cenumFromTo n_afx m_afy A.big [InlPrag=NOINLINE] :: () -> [Int] A.big = \ (u_abx :: ()) -> A.myEnumFromTo u_abx A.$s^2 lvl3_rEe 

    Ура.


    Что не работает?

    Выключить -Вернуться-лень

    Полное преобразование ланти плавает определения наружу. Он -O1 по умолчанию с -O1 или выше. Давайте попробуем отключить его с -fno-full-laziness . Однако это не работает.

    Обобщить. Если у вас есть постоянное значение, можете ли вы обобщить это на функцию некоторой переменной? Именование моей функции в вопросе twoTrues сразу же предполагает, что эта константа является третьей в последовательности zeroTrues , oneTrue , twoTrues , threeTrues и т. Д. – и это действительно так. Таким образом, обобщая twoTrues на функцию nTrues которая принимает параметр n и twoTrues , исключит один CAF из программы.

    В этом случае я рассматривал только случаи zeroTrues , oneTrue и twoTrues для моей программы, потому что это было все, что мне нужно, но моя программа, естественно, могла быть расширена для работы с nTrues для n > 2, поэтому обобщение на nTrues было бы означает, что имеет смысл «обобщать весь путь» пользователям zeroTrues , oneTrue и т. д. Это не всегда так.

    Примечание: все еще могут быть другие CAF, с которыми приходится иметь дело, как в коде, так и с помощью «оптимизаций» GHC (которые на самом деле не оптимизируются в этих патологических случаях).

    Однако этот ответ может потребовать больше работы программиста, чем это абсолютно необходимо. На самом деле нет необходимости обобщать, как показывает ответ Дона.

    С другой стороны, в некоторых случаях обобщение константы может сделать более понятным то, что вы на самом деле делаете, и помочь повторно использовать. Он может даже выявить способы более эффективного систематического расчета и / или более эффективного вычисления ряда ценностей.

    Заметка об этом конкретном случае (которая может быть проигнорирована): В этом конкретном случае я не хотел бы превращать nTrues в бесконечный список (который снова был бы CAF, снова возвращая исходную проблему!), А не как функцию. Одна из причин заключается в том, что, хотя twoTrues могут быть полезны в виде бесконечного списка, я не могу понять, как это было бы полезно (в моем приложении, в любом случае) для nTrues быть в виде бесконечного списка.

    С введением фиктивного параметра вы также должны заставить его выглядеть так, как результат действительно зависит от параметра. В противном случае умение GHC снова превратит его в CAF.

    Я предлагаю следующее:

     twoTrues u = map (++ (True : repeat False)) . trueBlock <$> [(u `seq` 1)..] 

    Кажется, это давняя проблема: http://hackage.haskell.org/trac/ghc/ticket/917 . И, на мой взгляд, критический.

    Вам нужно скрыть тот факт, что rhs является CAF от оптимизатора. Что-то вроде этого должно это сделать.

     twoTrues :: () -> [[[Bool]]] twoTrues u = map (++ (True : repeat (false u))) . trueBlock <$> [1..] {-# NOINLINE false #-} false :: () -> Bool false _ = False 

    Самое простое решение – рассказать компилятору о его встраивании. (Примечание: этот ответ не проверен. Если он не работает, прокомментируйте ниже).

    Даже если (предположительно) компилятор отказывается встраивать его по какой-либо причине, вместо этого вы можете использовать cpp , #defining:

     #define twoTrues (map (++ (True : repeat False)) . trueBlock <$> [1..]) 

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

    Опция -cpp указывает GHC на предварительную обработку входного файла с помощью cpp.

    Вложение означало бы дублирование кода n раз, если вы ссылаетесь на twoTrues в n> 1 местах. Однако, хотя это теоретически нежелательно, это, вероятно, не будет значительной проблемой на практике.

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

    Хотя я объявил здесь параметр, мне неинтересно, что это такое, и я не собираюсь ничего делать с его значением.

    Вы не интересны в этом, потому что () не имеет ничего интересного; вы ничего не собираетесь с этим делать, потому что вы ничего не можете сделать с помощью () .

    Проблема заключается в том, что компилятор имеет право оптимизировать его, поскольку есть только одно возможное значение, поэтому его использование всегда предсказуемо, и поэтому почему бы не предположить его? Но он возвращает его в CAF и делает эту идею неэффективной.

    К счастью, есть еще один способ сделать это. Посмотрите на следующую модификацию twoTrues :

     twoTrues :: a -> [[[Bool]]] twoTrues _ = map (++ (True : repeat False)) . trueBlock <$> [1..] 

    Теперь вы можете использовать twoTrues следующим образом:

     map concat $ twoTrues() 

    Так как a – параметр неиспользуемого типа, вызывающий может передать что угодно. И потому, что вы не знаете, что это было бы, вы не представляете, что вы можете с этим сделать. Это фактически заставляет вас игнорировать его ценность. Поэтому он в основном заявляет то же самое заявление, о котором я говорил ранее.

    Из-за этого вы можете передать любую вещь (в том числе undefined ) этой функции. Но это не имеет значения, и на самом деле именно эта возможность делает этот трюк работоспособным, поскольку компилятор больше не может предсказать, как эта функция используется. Когда пользователь видит эту функцию, они должны знать, что вы собираетесь здесь сказать, и завершить передачу () является самым простым, но даже если они не передают что-то еще, это ничего не сломает, и поскольку Haskell ленив, дополнительный параметр никогда не может быть оценен вообще.

    Итак, что, если () используется в результате? Это еще хуже. Поскольку return () означает, что ваша функция вообще ничего не делает (в Haskell все эффекты функции должны быть представлены в возвращаемом значении), компилятор имеет право заключить, что ваша функция не нужна.

    Вывод: () как тип не должны появляться в сигнатурах типов, если они не используются с каким-либо другим типом (т.е. в IO () ).

    РЕДАКТИРОВАТЬ

    Теперь можно задаться вопросом, существует ли только один способ реализации a -> String из String , почему компилятор не может заключить, что они одинаковы. Ответ оказывается, что у вас есть два способа реализовать это.

     usual :: a -> String usual _ = "Hello World!" unusual :: a -> String unusual a = seq a "Hello World!" 

    Для почти всех входных данных usual value = unusual value , но usual undefined является "Hello World!" в то время как unusual undefined не undefined .

    С человеческой точки зрения unusual довольно необычна, потому что она вынуждает оценивать значение, не связанное с конечным результатом. Если в любом случае вам понадобится такая вещь, просто вызвать seq будет проще. Кроме того, поскольку Haskell по умолчанию ленив, если вы хотите определить строгую функцию, вам лучше документировать это поведение. Поэтому, если вы видите такую ​​подпись без дополнительной документации, вы имеете право предположить, что она реализована usual способом.

    Давайте будем гением компьютера.