Data.Sequence.Seq ленивый параллельный экземпляр Functor

Question

Мне нужна параллельная (но ленивая) версия fmap за Seq от Data.Sequence пакет. Но пакет не экспортирует Seq конструкторы данных. Так что я не могу просто обернуть это newtype и реализовать Functor непосредственно для newtype,

Могу ли я сделать это без переписывания всего пакета?

Answer 1

Лучшее, что вы можете сделать, это, вероятно, splitAt последовательность в куски, fmap по каждому куску, а затем сложите части вместе. Seq представляется в виде дерева пальцев, поэтому его базовая структура не особенно подходит для параллельных алгоритмов - если вы разделите его по естественной структуре, последовательные потоки будут получать все большие и большие фрагменты. Если вы хотите попробовать, вы можете скопировать определение FingerTree введите из Data.Sequence источник и использование unsafeCoerce конвертировать между ним и Seq, Возможно, вы захотите отправить первые несколько Deep узлы в один поток, но тогда вам придется очень тщательно подумать об остальном. Пальцевые деревья могут быть очень далеки от веса, прежде всего потому, что 3^n растет асимптотически быстрее, чем 2^n; Вы должны принять это во внимание, чтобы сбалансировать работу между потоками.

Есть по крайней мере два разумных способа разделить последовательность, предполагая, что вы используете splitAt:

1. Разделите все это, прежде чем разбивать вычисления на потоки. Если вы сделаете это, вы должны разделить его слева направо или справа налево, потому что разделять маленькие кусочки дешевле, чем разделять большие, а затем разбивать их. Вы должны добавить результаты аналогичным образом.

2. Разделить его рекурсивно на несколько потоков. Это может иметь смысл, если вы хотите много кусков или больше потенциальной лени. Разделите список рядом с серединой и отправьте каждый фрагмент в цепочку для дальнейшего разделения и обработки.

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

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

Answer 2

Я нашел решение, но на самом деле оно не так эффективно.

-- | A combination of 'parTraversable' and 'fmap', encapsulating a common pattern:
--
-- > parFmap strat f = withStrategy (parTraversable strat) . fmap f
--
parFmap         :: Traversable t => Strategy b -> (a -> b) -> t a -> t b
parFmap strat f = (`using` parTraversable strat) . fmap f

-- | Parallel version of '<$>'
(<$|>) :: Traversable t =>  (a -> b) -> t a -> t b
(<$|>) = parFmap rpar