Error de "programación en Haskell" en la función de sat

Question

Estoy en el capítulo 8 de la programación de Graham Hutton en Haskell y estoy copiando el código y probándolo en GHC.

Ver las diapositivas aquí: http://www.cis.syr.edu/~sueo/cis352/chapter8.pdf en particular diapositiva 15

El código relevante He copiado hasta ahora es:

type Parser a = String -> [(a, String)] 
pih_return :: a -> Parser a 
pih_return v = \inp -> [(v, inp)] 
failure :: Parser a 
failure = \inp -> [] 
item :: Parser Char 
item = \inp -> case inp of 
        [] -> [] 
     (x:xs) -> [(x,xs)] 
parse :: Parser a -> String -> [(a, String)] 
parse p inp = p inp 
sat :: (Char -> Bool) -> Parser Char 
sat p = do x <- item 
      if p x then pih_return x else failure 

me han cambiado el nombre de la función return del libro para pih_return para que no entre en conflicto con la función Prelude return.

Los errores están en la última función sat. He copiado esto directamente del libro.

Como podrán ver p es una función Char-Bool (por ejemplo isDigit) y x es de tipo [(Char, String)], así que ese es el primer error.

Entonces pih_return toma un valor v y devuelve [(v, inp)] donde inp es una String. Esto causa un error en sat porque el v que se está pasando es x que no es un Char.

he llegado con esta solución, al incluir explícitamente en inpsat

Es esta la mejor manera de resolver el problema?

Answer 1

El primer sat no puede funcionar, Parser debe ser una mónada para utilizar la notación do. Para que sea una instancia de mónada, se debe usar newtype.

No soy dueño del libro, pero supongo que el autor quería comenzar con un tipo de analizador simple y luego extenderlo a una mónada completa y sospecho que ha confundido las definiciones de las versiones no monádicas con una de la mónada Parser (sat) y se perdió la declaración de la instancia de la mónada en el camino.

Hay un código del capítulo disponible on the author's web site donde se ha definido una instancia de mónada para Parser.

Si tiene que escribir una función sat por la simple tipo I Parser prefiero hacerlo en lambda-estilo (como item) y evitar por completo las mónadas (notado que el original sat 's do bloque era una mónada y Parser el tuyo es una mónada List?). Y creo que tiene un error en su versión sat: en lugar de pih_return (fst x) inp, creo que debería ser pih_return (fst x) (snd x).

Answer 2

A las diapositivas les falta la implementación de la clase de tipo Monad para el tipo Parser.

Con esa declaración, la notación do es correcta; x <- item en realidad realiza el desenvolvimiento correcto de [(Char, String)] a (Char, String).

Me parece que no puede conseguir esta definición sin compilar para ver el error, pero es un comienzo:

instance Monad (Parser a) where 
    return x = pih_return x 
    -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b 
    p >>= f = \inp -> case p inf of 
         [] -> [] 
         (x:xs) -> (f x) xs -- this line is probably wrong 
    fail message = [] -- message is ignored 

Answer 3

No se puede utilizar la notación do sin una mónada, y no se puede hacer una instancia de mónada a menos que use data o newtype, y no puede usar data o newtype a menos que introduzca un constructor de valores molestos. Sin lugar a dudas, el constructor de valores se ha omitido porque es molesto.

En el siguiente ejemplo, puede ver que he usado newtype y he introducido el molesto constructor de valores Parser. Esto es lo que hace que funcione la declaración instance, y en este punto puede usar no solo do -notación sino también el estándar monádico return y fail.

Este código se compila sin errores o advertencias:

module P 
where 

newtype Parser a = Parser (String -> [(a, String)]) 
instance Monad Parser where 
    return a = Parser $ \inp -> [(a, inp)] 
    fail _ = Parser $ \_ -> [] 
    Parser f >>= k = Parser $ \inp -> 
    [(b, inp'') | (a, inp') <- f inp, let Parser g = k a, (b, inp'') <- g inp'] 

item :: Parser Char 
item = Parser $ \inp -> case inp of 
          [] -> [] 
          (x:xs) -> [(x,xs)] 
parse :: Parser a -> String -> [(a, String)] 
parse (Parser p) inp = p inp 
sat :: (Char -> Bool) -> Parser Char 
sat p = do x <- item 
      if p x then return x else fail "predicate not satisfied" 

Answer 4

estoy leyendo el mismo libro y llegó al mismo problema cuando se trata de hacer los ejercicios. Revertí de usar la notación 'do ...' a >> >>. Para cualquier persona interesada encerré mi código hasta usar la función nat. Arreglé todas mis funciones con a y cambié >> = a >>> = para evitar colisiones de nombres con preludio.

type AParser a = String -> [(a, String)] 
areturn :: a -> AParser a 
areturn v = \inp -> [(v, inp)] 
afailure :: AParser a 
afailure = \inp -> [] 
aitem :: AParser Char 
aitem = \inp -> case inp of 
        [] -> [] 
        (x:xs) -> [(x, xs)] 
aparse :: AParser a -> String -> [(a, String)] 
aparse p inp = p inp 
(>>>=) :: AParser a -> (a -> AParser b) -> AParser b 
p >>>= f = \inp -> case aparse p inp of 
        [] -> [] 
        [(v, out)] -> aparse (f v) out 
(+++) :: AParser a -> AParser a -> AParser a 
p +++ q = \inp -> case aparse p inp of 
        [] -> aparse q inp 
        [(v, out)] -> [(v, out)] 
asat :: (Char -> Bool) -> AParser Char 
asat p = aitem >>>= (\x -> if p x then areturn x else afailure) 
adigit :: AParser Char 
adigit = asat isDigit 
amany :: AParser a -> AParser [a] 
amany p = amany1 p +++ areturn [] 
amany1 :: AParser a -> AParser [a] 
amany1 p = p >>>= (\v -> (amany p) >>>= (\vs -> areturn (v:vs))) 
anat :: AParser Int 
anat = amany1 adigit >>>= (\xs -> areturn (read xs))