Как создать таблицу (Data.Сопоставить) строгую в haskell?

#performance #haskell #data-structures #compile-time #strictness

#Производительность #haskell #структуры данных #время компиляции #строгость

Вопрос:

Для изучения Haskell (хороший язык) Я пытаюсь решить проблемы из Spoj.

У меня есть таблица с 19000 элементами, все из которых известны во время компиляции. Как я могу сделать таблицу строгой с помощью ‘seq’? Вот (сильный) упрощенный пример из моего кода.

 import qualified Data.Map as M

-- table = M.fromList . zip "a..z" $ [1..]  --Upps, incorrect. sorry
table = M.fromList . zip ['a'..'z'] $ [1..]

1. Знаете ли вы это и почему вам нужно, чтобы она была строгой? Если нет, я бы сказал YAGNI.

2. Насколько я вижу, это всего лишь 4 элемента?

3. Что именно вы хотите сделать строгим? Элементы, хранящиеся на карте? Построение самой карты? И почему?

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

5. @Jogusa Я думаю, будет очень сложно убедить ghc создать таблицу во время компиляции. Если вам абсолютно необходимо, то шаблон Haskell мог бы это сделать, но не используя Data.Map. Но почему это плохо с небольшим дополнительным временем при первом доступе?

Ответ №1:

Я думаю, вы ищете deepseq в Control.DeepSeq , который используется для принудительной полной оценки структур данных.

Ее сигнатура типа deepseq :: NFData a => a -> b -> b , и она работает, полностью оценивая свой первый аргумент, прежде чем возвращать второй.

 table = t `deepseq` t
  where t = M.fromList . zip ['a'..'z'] $ [1..]

Обратите внимание, что здесь все еще остается некоторая лень. table не будет оцениваться, пока вы не попытаетесь ее использовать, но в этот момент будет оценена вся карта.

Обратите внимание, что, как указал luqui, Data.Map уже является строгой в своих ключах, поэтому делать это имеет смысл, только если вы хотите, чтобы она была строгой и в своих значениях.

1. Данные. Карта является строгой в своих ключах, поэтому это вообще ничего не делает.

2. @luqui: Да, но она не является строгой по своим значениям. Это.

3. Что в данном случае ничего не делает. Хм … а может и нет. Это не имело бы никакого эффекта, даже если бы список значений был конечным [1..10^10^100] (потому что мы должны сравнивать с правильной конечной точкой, чтобы увидеть, должен ли список заканчиваться, таким образом, вводя каждое значение). Но поскольку она бесконечна, принудительное выполнение может в конечном итоге привести к выполнению некоторых вычислений. Ого … тонкая штука.

4. @luqui: Я предполагаю, что OP хранит что-то более интересное в своих значениях. В противном случае не было бы причин делать что-либо из этого.

5. Да, это имеет смысл. У меня произошел сбой метапознания.

Ответ №2:

Общий ответ таков: вы пишете некоторый код, который должен принудительно оценивать всю структуру данных. Например, если у вас есть список:

  strictList xs = if all p xs then xs else []
      where p x = x `seq` True

Я уверен, что уже существует какой-то класс type, который применял бы такое форсирование рекурсивно, и экземпляры для стандартных типов данных.