What is the correct signature for this function?

user_1827375 0
Viewed 110

This code fails to compile with this error

src/JsonParser.hs:33:37-62: error:
    * Couldn't match type `b1' with `b'
      `b1' is a rigid type variable bound by
        the type signature for:
          resultantRunParse :: forall b1. String -> Maybe (String, b1)
        at src/JsonParser.hs:29:5-52
      `b' is a rigid type variable bound by
        the type signature for:
          fmap :: forall a b. (a -> b) -> Parser a -> Parser b
        at src/JsonParser.hs:27:11-42
      Expected type: Maybe (String, b1)
        Actual type: Maybe (String, b)

The code:

import Prelude

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

instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap f (Parser p) = Parser resultantRunParse where
    -- THIS FUNCTION TYPE DECLARATION IS THE PROBLEM
    -- IF I REMOVE THE TYPE DECLARATION, IT WORKS
    resultantRunParse :: String -> Maybe (String, b)
    resultantRunParse input = 
      case p input of
        Nothing -> Nothing
        Just (remaining, parsed) -> Just (remaining, f parsed)

I tried the signature resultantRunParse :: forall b1. String -> Maybe (String, b1) suggested in the error message and that also didnt work.

Also, making the resultantRunParse = undefined and keeping the type signature also worked. Very strange!

What is the correct signature for this function?

haskell
2 Answers

The type signature must contain b, but it must be the same one as the b used in the enclosing function. This is impossible without scoped type variables:

https://wiki.haskell.org/Scoped_type_variables

To us this, add a comment to the top of your file:

{-# LANGUAGE ScopedTypeVariables #-}

Then, use an explicit forall b. in the enclosing function’s type signature.

Without scoped type variables, there is no way to write b in the type signature and make it the same b as the one used in the enclosing function.

(My personal recommendation is to just not use a type signature here. It is not necessary.)

user_822940

First get comfortable writing the instance by hand, then you can derive it. This type looks a lot like StateT, the state monad transformer where the order of the tuple is swapped.

type    StateT :: Type -> MonadTransformer
newtype StateT s m a = StateT (s -> m (a, s))

Your Functor Parser instance can be derived via it if you are willing to swap the order

{-# Language DerivingVia              #-}
{-# Language StandaloneKindSignatures #-}

import Control.Monad.State
import Data.Kind

type    Parser :: Type -> Type
newtype Parser a = Parser
  { runParser :: String -> Maybe (a, String)
  }
  deriving Functor
  via StateT String Maybe

You can derive more instances in this manner.

import Control.Applicative
import Control.Monad.Catch
import Control.Monad.Except
import Control.Monad.State
import Data.Kind
import Data.Monoid

newtype Parser a = Parser ..
  deriving
    ( Functor, Applicative, Alternative
    , Monad, MonadPlus, MonadFix, MonadThrow
    , MonadFail, MonadError (), MonadState String )
  via StateT String Maybe

  -- pointwise lifting
  --   (<>)   = liftA2 (<>)
  --   mempty = pure mempty
  -- deriving (Semigroup, Monoid, Num, Bounded)
  -- via Ap Parser a

  -- or Alternative
  --   (<>)   = (<|>)
  --   mempty = empty
  deriving (Semigroup, Monoid)
  via Ap Parser a

See the output of :instances command

  • :instances StateT String Maybe
  • :instances Ap Parser _
  • :instances Alt Parser _

The last two require partial type signatures :set -XPartialTypeSignatures -Wno-partial-type-signatures.

user_1658060
Related