1

I'm given the following code 

 newtype Parser a = Parser { parse :: String -> Maybe (a,String) }

   instance Applicative Parser where
   pure a = Parser $ \s -> Just (a,s)
   f <*> a = Parser $ \s ->
     case parse f s of
       Just (g,s') -> parse (fmap g a) s'
       Nothing -> Nothing

    instance Alternative Parser where
      empty = Parser $ \s -> Nothing
      l <|> r = Parser $ \s -> parse l s <|> parse r s

    satisfy :: (Char -> Bool) -> Parser Char
    satisfy p = Parser f
       where f [] = Nothing
             f (x:xs) = if p x then Just (x,xs) else Nothing

    ws :: Parser ()
    ws = pure () <* many (satisfy isSpace)

I know that ws parser removes leading spaces. But I need an explanation how exactly this is done. I don't understand the <* syntax ( I know <*>). Can some help me understand the syntax and why it is working ?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Tomer
  • 1,159
  • 7
  • 15
  • 2
    `<*` is a variant of `<*>` that performs the first action, then the second, and returns the result of the first one. https://tech.fpcomplete.com/haskell/tutorial/operators – Thilo Feb 15 '20 at 01:36
  • Also see https://stackoverflow.com/q/7746894/14955 – Thilo Feb 15 '20 at 01:38
  • But what function is get called by <* ? I have only <*> implemented – Tomer Feb 15 '20 at 02:09
  • 3
    `<*` is an `Applicative` method with a default definition of `(<*) = liftA2 const`. See https://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Base.html#Applicative – chepner Feb 15 '20 at 02:17
  • And `liftA2` itself *also* has a default definition in terms of `(<*>)`, just as `(<*>)` has a default definition in terms of `liftA2`. Define *either* `(<*>)` or `liftA2` in your instance declaration (along with `pure`), and you have a complete definition for `(<*>)`, `liftA2`, `(<*)`, and `(*>)`. – chepner Feb 15 '20 at 02:45
  • 1
    you haven't included the definition of `isSpace`. also, in Haskell, indentation matters. all lines in the same scope must start from the same column in the source file. – Will Ness Feb 15 '20 at 10:05

1 Answers1

1

No fear! It's easy, when we go by small steps, and see where it leads us. Next time, try doing it yourself.

(<*) = liftA2 const and liftA2 f x = (<*>) (fmap f x), so 

ws :: Parser ()
ws = pure () <* many (satisfy isSpace) 
     = {- (<*) = liftA2 const -}
     liftA2 const (pure ()) (many $ satisfy isSpace) 
     = {- liftA2 f x = (<*>) (fmap f x) -}
     fmap const (pure ()) <*> many (satisfy isSpace)
     = {- by Applicative laws -}
     (pure const <*> pure ()) <*> many (satisfy isSpace)
     = {- by homomorphism law of Applicatives -}
     pure (const ()) <*> many (satisfy isSpace)
     = {- with Applicative Do -}
     do { f <- pure (const ())
        ; r <- many (satisfy isSpace)
        ; pure (f r) }
     = {- by Law of `pure` being the identity, i.e. no-op, effects-wise -}
     do { let f = const ()
        ; r <- many (satisfy isSpace)
        ; pure (f r) }
     = {- by substitution -}
     do { r <- many (satisfy isSpace)
        ; pure (const () r) }
     =
     do { _ <- many (satisfy isSpace)
        ; pure () }
     =
     do { many (satisfy isSpace)
        ; pure () }
     = {- Monad Comprehension illustration -}
     [ () | _ <- many (satisfy isSpace) ]

(with the Applicative Do notation; to get the feeling for what this does. The Applicative Laws are enumerated at the above link as well.)

So it does what many (satisfy isSpace) does, except the computed value it returns is always ().

In pure functions, f a = () would completely ignore its second argument. We could call it as f (1 / 0) and it wouldn't care. But Applicative Functors express computations, and <*> combines computations fully known prior to the combination so that each one gets performed, whether its computed value is later used or not.

Will Ness
  • 70,110
  • 9
  • 98
  • 181