CODEWITHSUNDEEP
haskelltypeclass
Gosha A
Gosha A

Reputation: 4570

Typeclass for list <-> tuple conversion

I have a set of functions to convert between tuples and lists:

pack2 :: [a] -> (a, a)
pack2 (a:b:_) = (a, b)

unpack2 :: (a, a) -> [a]
unpack2 (a, b) = [a, b]

pack3 :: [a] -> (a, a, a)
pack3 (a:b:c:_) = (a, b, c)

unpack3 :: (a, a, a) -> [a]
unpack3 (a, b, c) = [a, b, c]

-- and so on

I want to generalize it a bit so that the following would be possible:

packN [1, 2, 3, 4] :: (Int, Int) -- => (1, 2)

unpackN (1, 2, 3) -- => [1, 2, 3]

I attempted to address it like this:

class Pack a b where
  packN :: a -> b
  unpackN :: b -> a

instance Pack [a] (a, a) where
  packN = pack2
  unpackN = unpack2

instance Pack [a] (a, a, a) where
  packN = pack3
  unpackN = unpack3

It does compile without any error (MultiParamTypeClasses, FlexibleInstances are enabled), however, when attempted to use, it fails:

> unpackN (1, 2)

<interactive>:84:1:
    Could not deduce (Pack a (t0, t1))
      arising from the ambiguity check for ‘it’
    from the context (Pack a (t, t2), Num t2, Num t)
      bound by the inferred type for ‘it’:
                 (Pack a (t, t2), Num t2, Num t) => a
      at <interactive>:84:1-14
    The type variables ‘t0’, ‘t1’ are ambiguous
    When checking that ‘it’
      has the inferred type ‘forall a t t1.
                             (Pack a (t, t1), Num t1, Num t) =>
                             a’
    Probable cause: the inferred type is ambiguous

How can I make it work?

Upvotes: 1

Views: 188

Answers (2)

Andr&#225;s Kov&#225;cs
Andr&#225;s Kov&#225;cs

Reputation: 30103

unpack has to somehow infer the return type from the input type, so let's look at ways to do that (pack always takes [a] as input, so there's no chance we can infer anything from that).

First, we can declare a functional dependency:

class Unpack tup a | tup -> a where
    unpack :: tup -> [a]

Here we promise that we only write instances for Unpack in such a way that a is always unambiguously inferable from tup. Thus, when we write unpack (a, b), the return type will be evident from the type of (a, b), and all will be well. 

instance Unpack (a, a) a where
   unpack (a, b) = [a, b]

Second, we can parametrize the class only by the tuple type, and compute the element type from it explicitly, using type families:

class Unpack tup where
    type Elem tup
    unpack :: tup -> [Elem tup]

instance Unpack (a, a) where
    type Elem (a, a) = a
    unpack (a, b) = [a, b]

However, there is one more thing to fix. Currently, unpack doesn't work without type annotations if the element type is polymorphic:

unpack (1, 2) -- type error

This is because numerals have type Num a => a, and (1, 2) could have type (Int, Float) too, which is not what we specified in our instance. Our instance Unpack (a, a) matches only when it is evident that we have the same concrete, monomorphic types in the tuple.

In general, an instance is chosen depending solely on the form of the instance heads (here the instance head is the tup type in instance Unpack tup), and only after that does GHC check whether the instance constraints hold. We can use this to our advantage: we can make sure that we have an instance even for the case when the types in the tuple are different, and then use the instance constraints to force the types to be the same nevertheless:

-- I assume we use the functional dependencies version here
instance a ~ b => Unpack (a, b) a where
    unpack (a, b) = [a, b]

Now unpack always works without annotations.

It could be a bit bothersome to write out all the type equality constraints for large tuples:

instance (a ~ b, b ~ c, c ~ d) => Unpack (a, b, c, d) a where
    unpack (a, b, c, d) = [a, b, c, d]

Fortunately we can write a shorthand for the equalities using ConstraintKinds and type families:

{-# LANGUAGE 
    ConstraintKinds, DataKinds, TypeOperators, TypeFamilies,
    MultiParamTypeClasses, FunctionalDependencies, UndecidableInstances #-}

import GHC.Exts

type family AllSame (xs :: [*]) :: Constraint where
    AllSame '[]  = ()
    AllSame '[a] = ()
    AllSame (a ': b ': xs) = (a ~ b, AllSame (b ': xs))

...

instance AllSame [a, b, c, d] => Unpack (a, b, c, d) a where
    unpack (a, b, c, d) = [a, b, c, d]

The thing to know here is that ConstraintKinds works by treating the tuple type as conjunction for constraints, and () as the empty constraint that is always satisfied. AllSame is just a type level function that expands to a constraint equivalent to what we wrote out by hand earlier.

Upvotes: 8

Random Dev
Random Dev

Reputation: 52280

Here is a version using type-families (maybe not in an idiomatic way) that solves your problem:

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies #-}

module Test where

pack2 :: [a] -> (a, a)
pack2 (a:b:_) = (a, b)

unpack2 :: (a, a) -> [a]
unpack2 (a, b) = [a, b]

pack3 :: [a] -> (a, a, a)
pack3 (a:b:c:_) = (a, b, c)

unpack3 :: (a, a, a) -> [a]
unpack3 (a, b, c) = [a, b, c]

class Pack b where
  type Element b :: *
  packN :: [Element b] -> b
  unpackN :: b -> [Element b]

instance Pack (a, a) where
  type Element (a,a) = a
  packN = pack2
  unpackN = unpack2

instance Pack (a, a, a) where
  type Element (a,a,a) = a
  packN = pack3
  unpackN = unpack3

so this will work:

unpackN ((1,2) :: (Int, Int))
> [1,2]

maybe this is a better example (as it does not share the generic numeral flaw ^^ ):

*Test> unpackN ('a','b')
"ab"
*Test> unpackN ('a','b','c')
"abc"

Upvotes: 2

Related Questions