2016-08-13 12 views
1
{-# LANGUAGE ScopedTypeVariables,BangPatterns #-} 

import qualified Data.Attoparsec.Internal as I 
import qualified Data.Attoparsec.Internal.Types as T 
import qualified Data.Vector.Unboxed as UVec 
import qualified Data.Vector.Unboxed.Mutable as UMVec 
import qualified Data.Vector as Vec 
import qualified Data.Vector.Mutable as MVec 
import qualified Data.Text as Text 
import qualified System.IO.Unsafe as Unsafe 

import Control.Monad.ST 
import Control.Monad.Primitive 

type Parser = T.Parser 

manyCPSVec :: Parser Text.Text Char -> Parser Text.Text (Vec.Vector Char) 
manyCPSVec parser = T.Parser $ \t pos more lose_fin win_fin -> 
     let arr = Unsafe.unsafePerformIO (MVec.new 1024) in 
     loop 0 arr t pos more lose_fin win_fin where 
      loop i (arr :: MVec.MVector RealWorld Char) t pos more lose_fin win_fin = 
       T.runParser parser t pos more lose win where 
        win t !pos more (a :: Char) = 
        Unsafe.unsafePerformIO (MVec.write arr i a) -- Here is the problem 
        loop (i+1) arr t pos more lose_fin win_fin 
        lose t pos more _ _ = 
         --x <- Vec.freeze arr 
         win_fin t pos more (Vec.empty) 

main = print "Hello" 

Я пытаюсь добавить в функциональность Attaparsec некоторые функции Vector, но я столкнулся с стеной.Как мутировать вектор, проходящий в функции стиля CPS?

Если Attoparsec не был написан с использованием CPS, я мог бы использовать functional unfoldr, но здесь это не вариант. Проблема в том, что все вызовы должны быть в положении хвоста здесь, и никакая функция не возвращается в стандартном смысле вещи, поэтому массивы должны передаваться как аккумуляторы.

Я попытался сделать это, используя монаду ST, но когда это не сработало, я попробовал выше, но даже в этом случае он не работает. Система типа Haskell действительно убивает меня здесь. Можно ли в любом случае отредактировать изменяемые массивы при программировании с помощью CPS?

Если это возможно сделать в монаде ST, я бы вдвойне оценил это.

Сообщения, сообщающие мне использовать структуры данных, отличные от массивов, хотя и будут опущены.

+0

Просто интересно, получается ли это быстрее, чем сбор списка и использование 'Vector.fromList'? – Michael

+0

Я думаю, что вы сможете найти способ сделать это в 'ST'. Задача будет эффективно работать с частичными результатами, но я подозреваю, что нет абсолютно эффективного способа их устранения. В частности, помните, что частичный результат может быть возобновлен несколько раз с разными входами, поэтому слишком много 'unsafePerformIO' может сломать ваш код. – dfeuer

+0

@ Майкл Да, совсем немного. Для синтаксического анализа целых чисел 10M имеет значение структура данных, которые вы используете. Используя [законченный парсер] (https://github.com/mrakgr/futhark/blob/parser_attempts/cps_parser_v5.hs) с вложенными векторами, он имеет дело с 10M ints в 7,6 с. С распакованным парсером он делает это за 4 секунды. Просто используя расширенный функциональный unoldr с коробочным вектором делает это в 2s. 'ResizeArray' в F # делает это в 1.2s. [Постоянный вектор] (https://hackage.haskell.org/package/persistent-vector) делает это в 9.8. Помимо решения F #, все они взорвали кучу на 100 М. Списки делают это задолго до 10M. –

ответ

0

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

manyCPSVec :: Parser Text.Text Char -> Parser Text.Text (Vec.Vector Char) 
manyCPSVec parser = T.Parser $ \t pos more lose_fin win_fin -> 
     let arr = Unsafe.unsafePerformIO (MVec.new 1024) in 
     loop 0 arr t pos more lose_fin win_fin where 
      loop i (arr :: MVec.MVector RealWorld Char) t pos more lose_fin win_fin = 
       T.runParser parser t pos more lose win where 
        win t !pos more (a :: Char) = 
        Unsafe.unsafePerformIO $ do 
         MVec.write arr i a 
         return $ loop (i+1) arr t pos more lose_fin win_fin 
        lose t pos more _ _ = 
        Unsafe.unsafePerformIO $ do 
         x <- Vec.freeze arr 
         return $ win_fin t pos more x 

Вышеуказанный тип проверен. Я забыл, что я не могу упорядочить инструкции вне блоков do в Haskell.