Creating Functor Class

Learn
#1

I am trying to define my own class of Functor from this My code is:

class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: liftA2 id
    liftA2 :: (a -> b -> c) -> f a -> f b -> f c
    liftA2 f x = (<*>) (fmap f x)
    (*>) :: f a -> f b -> f b
    a *> a2 = (id <$ a1) <*> a2
    (<*) :: f a -> f b -> f a
    (<*) = liftA2 const

I have hidden the functions from the Prelude and GHC.Base using:

import Prelude hiding (map, Maybe, Nothing, Just, (<*>))
import GHC.Base hiding (Functor, Maybe, Nothing, Just, map, (<*>), liftA2)

But I get the following error on the line (<*>) :: liftA2 id:

Could not deduce (Main.Applicative f0)
      from the context: Main.Applicative f
        bound by the type signature for:
                   (<*>) :: forall (f :: * -> *) {k} (liftA2 :: k -> *) (id :: k).
                            Main.Applicative f =>
                            liftA2 id

I also get a similar error using (<*>) in a1 *> a2 = (id <$ a1) <*> a2

Can anyone explain why this is happening?

Thanks,

Luke

#2

The error message is kind of terrible, but you probably meant to write:

    (<*>) :: f (a -> b) -> f a -> f b
    (<*>) = liftA2 id
1 Like
#3

By the way, you should probably just remove that whole import GHC.Base ... line. Only the module Prelude is loaded by default, so you only have to hide things from there. Now you import GHC.Base only to hide a bunch of stuff. It seems you’re never actually using anything from the GHC.Base module.

1 Like
#4

Now that we understand that (<*>) :: liftA2 id was a typo, let’s see what the computer saw.

The computer definitely saw a type sig. It had ::

In a type sig, lower case names mean type variables. They are also renamable. It is as though you wrote (<*>) :: g a

So it has nothing to do with the f in context, hence the error.

#5

This fixed the error in the class definition.

#6

Also have done this.

#7

That being said, I am now trying to create an instance for the list type:

instance Functor [] where
    fmap :: (a -> b) -> [a] -> [b]
    fmap = map

Having defined my own map function:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

And I get this error:

[1 of 2] Compiling Main             ( Functors.hs, interpreted ) [Source file changed]

Functors.hs:45:10: error:
    Duplicate instance declarations:
      instance Functor [] -- Defined at Functors.hs:45:10
      instance Functor [] -- Defined in ‘GHC.Base’
   |
45 | instance Functor [] where
   |          ^^^^^^^^^^
Failed, no modules loaded.


How do I hide the list constructor? Presumably I’ll have to define my own list constructor to do so, but how do I hide it.

Also, where is list defined in the Haskell source code? I can’t find any links describing this.

#8

Just ask ghci:

:info []

So the data type is indeed defined in GHC.Types, but not imported from there unless you explicitly import that module. Instead it is imported by Prelude and re-exported from there. You get to the defining module by clicking the # Source links in Haddock documentation on Hackage.

By the way, that is not the problem here. The problem is that there is apparently a second Functor class in scope, namely the one implicitly imported from Prelude. (Notice you did not hide Functor from the Prelude import!) You can get rid of that by prefixing your source file with

{-# LANGUAGE NoImplicitPrelude #-}

which will strip down the available names to a minimum (which surprisingly still contains the [] data type, presumably because it is mentioned in the first Haskell language report).

1 Like
#10

I added the pragma to the top of the file and defined Chars and Lists from the Haskell Source Code. The code is now as follows:

{-# LANGUAGE NoImplicitPrelude #-}

module MonadicParsingInHaskell where

import Data.Char

type String :: *
type String = [Char]

type Char :: *
data Char = GHC.Types.C# GHC.Prim.Char#

newtype Parser a = Parser (String -> [(a,String)])

item :: Parser Char
item = Parser (\cs -> case cs of
    ""     -> []
    (c:cs) -> [(c,cs)])

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

parse :: Parser a -> String -> [(a, String)]
parse (Parser p) = p

many   :: Parser a -> Parser [a]
many p  = many1 p +++ return []

many'   :: Parser a -> Parser [a]
many' p  = many p +++ MonadicParsingInHaskell.return []

instance Monad Parser where
      return :: a -> Parser a
      return a = Parser (\cs -> [(a,cs)])
      (>>=) :: Parser a -> (a -> Parser b) -> Parser b
      p >>= f  = Parser (\cs -> concat [parse (f a) cs' |
                                   (a,cs') <- parse p cs])

p :: Parser (Char,Char)
p  = do {c <- item; item; d <- item; MonadicParsingInHaskell.return (c,d)}

class MonadicParsingInHaskell.Monad m => MonadZero m where
      zero :: m a

class MonadZero m => MonadPlus m where
    (++) :: m a -> m a -> m a

instance MonadZero Parser where
      zero :: Parser a
      zero   = Parser (const [])

instance MonadPlus Parser where
      (++) :: Parser a -> Parser a -> Parser a
      p ++ q = Parser (\cs -> parse p cs ++ parse q cs)

(+++)  :: Parser a -> Parser a -> Parser a
p +++ q = Parser (\cs -> case parse (p MonadicParsingInHaskell.++ q) cs of
                               []     -> []
                               (x:xs) -> [x])

sat  :: (Char -> Bool) -> Parser Char
sat p = do {c <- item; if p c then return c else zero}

char :: Char -> Parser Char
char c = sat (c ==)

string       :: String -> Parser String
string ""     = return ""
string (c:cs) = do {char c; string cs; return (c:cs)}

many1  :: Parser a -> Parser [a]
many1 p = do {a <- p; as <- many p; Mreturn (a:as)}

sepby         :: Parser a -> Parser b -> Parser [a]
p `sepby` sep  = (p `sepby1` sep) +++ return []

sepby1 :: Parser a -> Parser b -> Parser [a]
p `sepby1` sep = do a <-p
                    as <- many (do {sep; p})
                    return (a:as)

chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl p op a = (p `chainl1` op) +++ return a

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = do {a <- p; rest a}
                    where
                       rest a = (do f <- op
                                    b <- p
                                    rest (f a b))
                                +++ return a

space :: Parser String
space = many1 (sat isSpace)

token  :: Parser a ->  Parser a
token p = do
    a <- p; space; return a

symb :: String -> Parser String
symb cs = token (string cs)

apply  :: Parser a -> String -> [(a,String)]
apply p = parse (do {space; p})

expr  :: Parser Int
expr = term `chainl1` addop

addop :: Parser (Int -> Int -> Int)
addop = do {symb "+"; return (+)} +++ do {symb "-"; return (-)}

mulop :: Parser (Int -> Int -> Int)
mulop = do {symb "*"; return (*)} +++ do {symb "/"; return (div)}

term :: Parser Int
expr = term `chainl1` addop

term :: Parser Int
term = factor `chainl1` mulop

factor :: Parser Int
factor = digit +++ do {symb "("; n <- expr; symb ")"; MonadicParsingInHaskell.return n}

digit :: Parser Int
digit = do {x <- token (sat isDigit); MonadicParsingInHaskell.return (ord x - ord '0')}

addop = do {symb "+"; return (+)} +++ do {symb "-"; return (-)}
mulop = do {symb "*"; Meturn (*)} +++ do {symb "/"; return (div)}

The error I am now getting is:

GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )

MonadicParsingInHaskell.hs:13:1: error:
    parse error (possibly incorrect indentation or mismatched brackets)
   |
13 | newtype Parser a = Parser (String -> [(a,String)])
   | ^
Failed, no modules loaded.

The problem is coming from `Line 13` - the problem is coming from: newtype Parser a = Parser (String -> [(a,String)])

I am following this paper, by the way. If that helps.

Sorry, this is a different project I am working on, but the pragma fit equally better so I thought it would fit in this thread relatively well. Thanks again Olaf.

#11

A parse error possibly incorrect indentation or mismatched brackets almost never originates on the line reported by GHC. Almost always the problem lies in the code above. I suspect the magic hash # confuses the Haskell parser. Observe that at the top of the Data.Char module source there is the MagicHash extension enabled.

Anyways, why are you re-defining Char and String? Just importing them from Data.Char resp. GHC.Base should be enough. With an additional import

import GHC.Base (String)

and the superfluous definitions removed, my GHC 8.8.4 does not choke at the Parser newtype declaration.

My compiler instead complains about concat not being in scope. Adding

import Data.List (concat)

fixes that. Some further comments:
Merge parse into the declaration of the Parser newtype like so.

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

The concat function and list comprehensions is what makes the Monad instance of List

instance Monad [] where
    return x = [x]
    xs >>= f = concat [f x | x <- xs]

So you might leverage that in the Monad instance of Parser

p >>= f = Parser (\cs -> 
    parse p cs >>= \(a,cs') -> parse (f a) cs')

Here the >>= on the second line is the bind of the list monad. Notice also that the one-element list in the definition of return is the return of the list monad. This goes to show that the [] (allowing multiple parse results or none) can be replaced by other monads like Maybe, yielding other parsers.

newtype ParseT m a = ParseT {parse :: String -> m (a,String)}
instance Monad m => Monad (ParseT m) where
    return a = ParseT (\cs -> return (a,cs))
    p >>= f = ParseT (\cs ->
        parse p cs >>= \(a,cs') -> parse (f a) cs')
type Parser = ParseT []

And later on you’ll notice that ParseT is just StateT String.

1 Like