Haskell Bytestrings: ¿Cómo hacer coincidir el patrón?

pattern-matching pattern-synonyms

Question

Soy un novato de Haskell, y tengo un poco de problemas para descubrir cómo ByteString un ByteString . La versión [Char] de mi función se ve así:

dropAB :: String -> String
dropAB []       = []
dropAB (x:[])   = x:[]
dropAB (x:y:xs) = if x==''a'' && y==''b''
                  then dropAB xs
                  else x:(dropAB $ y:xs) 

Como se esperaba, esto filtra todas las apariciones de "ab" de una cadena. Sin embargo, tengo problemas al intentar aplicar esto a un ByteString .

La versión ingenua.

dropR :: BS.ByteString -> BS.ByteString
dropR []         = []
dropR (x:[])     = [x]
<...>

rendimientos

Couldn''t match expected type `BS.ByteString''
       against inferred type `[a]''
In the pattern: []
In the definition of `dropR'': dropR [] = []

[] es claramente el culpable, como lo es para una String normal String no una ByteString . Sustituir en BS.empty parece ser lo correcto pero da "Nombre calificado en la posición de enlace: BS.empty". Dejándonos probar

dropR :: BS.ByteString -> BS.ByteString
dropR empty              = empty        
dropR (x cons empty)     = x cons empty
<...>

esto da "error de análisis en el patrón" para (x cons empty) . Realmente no sé qué más puedo hacer aquí.

Como nota al margen, lo que estoy tratando de hacer con esta función es filtrar un carácter UTF16 específico de algún texto. Si hay una forma clara de lograrlo, me encantaría escucharlo, pero este error de coincidencia de patrón parece ser algo que un haskeller novato debería entender realmente.

Answer 1

La última versión de GHC (7.8) tiene una característica llamada sinónimos de patrón que se puede agregar al ejemplo de gawi:

{-# LANGUAGE ViewPatterns, PatternSynonyms #-}

import Data.ByteString (ByteString, cons, uncons, singleton, empty)
import Data.ByteString.Internal (c2w)

infixr 5 :<

pattern b :< bs <- (uncons -> Just (b, bs))
pattern Empty   <- (uncons -> Nothing)

dropR :: ByteString -> ByteString
dropR Empty          = empty
dropR (x :< Empty)   = singleton x
dropR (x :< y :< xs)
  | x == c2w ''a'' && y == c2w ''b'' = dropR xs
  | otherwise                    = cons x (dropR (cons y xs))

Yendo más allá, puede abstraer esto para que funcione en cualquier clase de tipo (esto se verá mejor cuando / si obtenemos sinónimos de patrones asociados ). Las definiciones de patrones siguen siendo las mismas:

{-# LANGUAGE ViewPatterns, PatternSynonyms, TypeFamilies #-}

import qualified Data.ByteString as BS
import Data.ByteString (ByteString, singleton)
import Data.ByteString.Internal (c2w)
import Data.Word

class ListLike l where
  type Elem l

  empty  :: l
  uncons :: l -> Maybe (Elem l, l)
  cons   :: Elem l -> l -> l

instance ListLike ByteString where
  type Elem ByteString = Word8

  empty  = BS.empty
  uncons = BS.uncons
  cons   = BS.cons

instance ListLike [a] where
  type Elem [a] = a

  empty         = []
  uncons []     = Nothing
  uncons (x:xs) = Just (x, xs)
  cons          = (:)

en cuyo caso, dropR puede funcionar tanto en [Word8] como en ByteString :

-- dropR :: [Word8]    -> [Word8]
-- dropR :: ByteString -> ByteString
dropR :: (ListLike l, Elem l ~ Word8) => l -> l
dropR Empty          = empty
dropR (x :< Empty)   = cons x empty
dropR (x :< y :< xs)
  | x == c2w ''a'' && y == c2w ''b'' = dropR xs
  | otherwise                    = cons x (dropR (cons y xs))

Y por el gusto de hacerlo:

import Data.ByteString.Internal (w2c)

infixr 5 :•    
pattern b :• bs <- (w2c -> b) :< bs

dropR :: (ListLike l, Elem l ~ Word8) => l -> l
dropR Empty              = empty
dropR (x   :< Empty)     = cons x empty
dropR (''a'' :• ''b'' :• xs) = dropR xs
dropR (x   :< y   :< xs) = cons x (dropR (cons y xs))

Puedes ver más en mi post sobre sinónimos de patrones.

Answer 2

Los patrones utilizan constructores de datos. http://book.realworldhaskell.org/read/defining-types-streamlining-functions.html

Su empty es solo un enlace para el primer parámetro, podría haber sido x y no cambiaría nada.

No puede hacer referencia a una función normal en su patrón, por lo que (x cons empty) no es legal. Nota: Supongo que (cons x empty) es realmente lo que querías decir, pero esto también es ilegal.

ByteString es muy diferente de String . String es un alias de [Char] , por lo que es una lista real y el operador : puede utilizarse en patrones.

ByteString es Data.ByteString.Internal.PS !(GHC.ForeignPtr.ForeignPtr GHC.Word.Word8) !Int !Int (es decir, un puntero a un carácter nativo * + desplazamiento + longitud). Como el constructor de datos de ByteString está oculto, debe usar funciones para acceder a los datos, no a los patrones.

Aquí una solución (seguramente no la mejor) para su problema de filtro UTF-16 usando el paquete de text :

module Test where

import Data.ByteString as BS
import Data.Text as T
import Data.Text.IO as TIO
import Data.Text.Encoding

removeAll :: Char -> Text -> Text
removeAll c t =  T.filter (/= c) t

main = do
  bytes <- BS.readFile "test.txt"
  TIO.putStr $ removeAll ''c'' (decodeUtf16LE bytes)

Answer 3

Para esto, coincidiría con el resultado de uncons :: ByteString -> Maybe (Word8, ByteString) .

La coincidencia de patrones en Haskell solo funciona en constructores declarados con ''data'' o ''newtype''. El tipo ByteString no exporta los constructores que usted no puede hacer coincidir con el patrón.

Answer 4

Puedes usar patrones de vista para tales cosas

{-# LANGUAGE ViewPatterns #-}    
import Data.ByteString (ByteString, cons, uncons, singleton, empty)
import Data.ByteString.Internal (c2w) 

dropR :: ByteString -> ByteString
dropR (uncons -> Nothing) = empty
dropR (uncons -> Just (x,uncons -> Nothing)) = singleton x
dropR (uncons -> Just (x,uncons -> Just(y,xs))) =
    if x == c2w ''a'' && y == c2w ''b''
    then dropR xs
    else cons x (dropR $ cons y xs)

Answer 5

Solo para solucionar el mensaje de error que recibió y lo que significa:

Couldn''t match expected type `BS.ByteString''
       against inferred type `[a]''
In the pattern: []
In the definition of `dropR'': dropR [] = []

Así que el compilador esperaba que su función fuera de tipo: BS.ByteString -> BS.ByteString porque le dio ese tipo en su firma. Sin embargo, se dedujo (al observar el cuerpo de su función) que la función es en realidad de tipo [a] -> [a] . Hay un desajuste allí por lo que el compilador se queja.

El problema es que estás pensando en (:) y [] como azúcar sintáctica, cuando en realidad son solo los constructores para el tipo de lista (que es MUY diferente de ByteString).