CODEWITHSUNDEEP
haskellpolymorphismtype-variables
ErikR
ErikR

Reputation: 52029

constraining type variables to concrete types

I have this monomorphic code:

import Data.Array.MArray
import Data.Array.IO (IOUArray)
import Data.Ix (Ix)

push :: IOUArray Int Int -> Int -> [Int] -> IO Int
push stack top [] = return top
push stack top (k:ks) = do
  v <- readArray stack k
  if v >= 0 then push stack top ks
            else do writeArray stack k top
                    push stack k ks

A fully polymorphic signature for push would be:

push :: (MArray a e m, Ix e, Num e)  => a e e -> e -> [e] -> m e

But I tried to write these partially polymorphic signatures:

push :: MArray a e m => a Int e -> Int -> [Int] -> m Int
push :: MArray a e m => a Int Int -> Int -> [Int] -> m Int
push :: MArray a Int m => a Int Int -> Int -> [Int] -> m Int
push :: (MArray a e m, e ~ Int) => a e e  -> e -> [e] -> m e

and I get errors like can't deduce (e ~ Int), can't deduce (MArray a Int m) ... and Non type-variable argument in constraint, Illegal equational constraint

Is there a way to constrain the type variable e in the first signature to a concrete type like Int?

Upvotes: 2

Views: 110

Answers (2)

crockeea
crockeea

Reputation: 21811

The first signature

push :: MArray a e m => a Int e -> Int -> [Int] -> m Int

doesn't work because you are reading an array element v <- readArray stack k which has type e, but then compare it to 0, which is an Int or Integer (edit: really any Num).

The second signature

push :: MArray a e m => a Int Int -> Int -> [Int] -> m Int

doesn't work because you say that a e m is an instance of MArray, but then try to use a a Int Int. GHC tries to unify the required constraint with the given constraint, so it tries to match e with Int.

Ganesh's answer resolves the other two signatures.

Upvotes: 3

Ganesh Sittampalam
Ganesh Sittampalam

Reputation: 29100

The third signature works if you enable FlexibleContexts (as the error suggests):

{-# LANGUAGE FlexibleContexts #-}
import Data.Array.MArray
import Data.Array.IO (IOUArray)
import Data.Ix (Ix)

push :: MArray a Int m => a Int Int -> Int -> [Int] -> m Int
-- push :: IOUArray Int Int -> Int -> [Int] -> IO Int
push stack top [] = return top
push stack top (k:ks) = do
  v <- readArray stack k
  if v >= 0 then push stack top ks
            else do writeArray stack k top
                    push stack k ks

There's some discussion of this extension on the Haskell Prime wiki.

The fourth signature works with TypeFamilies to allow the e ~ Int constraint:

{-# LANGUAGE TypeFamilies #-}
import Data.Array.MArray
import Data.Array.IO (IOUArray)
import Data.Ix (Ix)

push :: (MArray a e m, e ~ Int) => a e e  -> e -> [e] -> m e
-- push :: IOUArray Int Int -> Int -> [Int] -> IO Int
push stack top [] = return top
push stack top (k:ks) = do
  v <- readArray stack k
  if v >= 0 then push stack top ks
            else do writeArray stack k top
                    push stack k ks

In this particular case I think it has exactly the same effect on type checking of calling contexts as the other working signature with FlexibleContexts, but in general having a type variable with an equality constraint is not quite the same as having a concrete type.

Upvotes: 5

Related Questions