sat 함수의 "Programming in Haskell"오류가 발생했습니다.

Question

저는 Graham Hutton이 Haskell에서 프로그래밍하고있는 8 장에 있습니다. 코드를 복사하고 GHC에서 테스트하고 있습니다.

여기에 슬라이드를 참조하십시오 http://www.cis.syr.edu/~sueo/cis352/chapter8.pdf 특히 슬라이드 15

지금까지 복사 한 관련 코드는 다음과 같습니다

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 

나는 pih_return에 책에서 return 함수의 이름을 변경 한 그래서 그것은 Prelude return 함수와 충돌하지 않습니다.

오류는 마지막 기능 sat에 있습니다. 이 책에서 직접 복사했습니다. 그 첫 번째 오류 그래서

당신은 아마 p를 볼 수있는 바와 같이, 유형 [(Char, String)]이다 Char에서 (예를 들어, isDigit) Bool 및 x하는 기능입니다.

pih_return 값이 v이고 이 String 인 경우 [(v, inp)]을 반환합니다. 이 경우 v이 전달되는 x이 Char이 아니므로 sat에 오류가 발생합니다.

나는 명시 적으로이 문제를 해결하는 가장 좋은 방법입니다 sat

sat :: (Char -> Bool) -> Parser Char 
sat p inp = do x <- item inp 
       if p (fst x) then pih_return (fst x) inp else failure inp 

에 inp을 포함하여,이 솔루션과 함께 올라와있다?

Answer 1

첫 번째 sat은 작동하지 않으며 Parser은 do 표기법을 사용하려면 모나드 여야합니다. Monad 인스턴스로 만들려면 newtype을 사용해야합니다.

필자는이 책을 소유하고 있지 않지만 필자는 간단한 파서 유형으로 시작한 다음 나중에 전체 모나드로 확장하려고한다고 가정합니다. 모나드가 아닌 버전의 정의가 하나의 Parser 모나드 (sat)와 모나드 인스턴스 선언을 놓쳤습니다.

on the author's web site에서 Parser에 대한 모나드 인스턴스가 정의 된 코드가 있습니다. 당신은 내가 아니라 (item로) 람다 식에 그것을 전적으로 모나드를 피하려는 간단한 Parser 유형에 대한 sat 함수를 작성해야하는 경우

는 (원래 sat의 do 블록이 Parser 모나드 것을 발견하고 너의 것은 List 모나드인가?). 그리고 내가 sat 버전에 버그가 있다고 생각하면 pih_return (fst x) inp이 아닌 pih_return (fst x) (snd x)이되어야한다고 생각합니다.

Answer 2

슬라이드에 Parser 유형의 Monad 유형 지정이 구현되어 있지 않습니다.

해당 선언을 사용하면 do 표기법이 정확합니다. x <- item은 실제로 [(Char, String)]에서 (Char, String)으로 올바른 언 래핑을 수행합니다.

내가 오류를보고 그것을 컴파일하지 않고이 정의를 얻이 수없는 것 그러나 그것은 시작이다 : 당신은 모나드없이 do 표기법을 사용할 수 없습니다

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

, 당신은 할 수 없습니다 data 또는 newtype을 사용하거나 성가신 값 생성자를 사용하지 않으면 또는 newtype을 사용할 수 없다면 모나드 인스턴스를 사용하십시오. 의심 할 여지없이 값 생성자는 이 짜증나기 때문에 생략되었습니다.

아래 예제에서 나는 newtype을 사용했고 성가신 값 생성자 Parser을 소개했습니다. 이것이 instance 선언을 만드는 것입니다.이 시점에서 do -notation뿐만 아니라 표준 모나드 return 및 fail을 사용할 수 있습니다.

이 코드는 오류 또는 경고없이 컴파일 : 내가 바로 그 책을 읽고 excercises을하려고 할 때 같은 문제에 도착 해요

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

. 나는 'do ...'표기법을 >> =에 사용하는 것을 되돌 렸습니다. 누구든지 관심을 끌기 위해 내 코드를 nat 함수를 사용하여 묶었습니다. 나는 모든 함수 앞에 a를 붙 였고 prelude와의 이름 충돌을 피하기 위해 >> = to >>> =로 바꿨다.

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))