Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Ad-hoc cotuples in Haskell

Tags:

haskell

In Haskell, it is easy to write functions that act on or return tuples of things, e.g. the prelude function splitAt:

splitAt :: Int -> [a] -> ([a], [a]) 

but is there no easy, convenient, way of writing functions that act on or result in cotuples of things? E.g. a function that returns an Int or a Double. As a concrete example, let's say I want to write a function

MyDivision :: Int -> Int -> (Int + Double)

where + is my symbol for cotupling, so MyDivision x y returns x/y as an Int if the division results in an integer but as a Double if the division does not result in an integer.

So far, it seems that I have two choices, either declare a new datatype

data IntOrDouble = AnInt Int | ADouble Double

or use

Either Int Double

where the first alternative requires a lot of typing and thinking of names and the second alternative quickly gets messy when you have larger cotuples and get types looking like

Either (Either a (Either b c)) (Either (Either d f) g)

Now, if I had a a cotuple type, say

a + b + c + d

I would like to be able to form functions

f :: (a + b + c + d) -> e
g :: (a + b + c + d) -> (e + f + g + h)

by just supplying functions

f1 :: a -> e, f2 :: b -> e, f3 :: c -> e, f4 :: d -> e
g1 :: a -> e, g2 :: b -> f, g3 :: c -> g, g4 :: d -> h

and setting

f = f1 + f2 + f3 + f4
g = g1 <+> g2 <+> g3 <+> g4

or something of the like.

Is this possible?

like image 589
Calle Avatar asked Jun 24 '14 20:06

Calle


People also ask

What is ad hoc polymorphism in Haskell?

Ad-hoc polymorphism refers to when a value is able to adopt any one of several types because it, or a value it uses, has been given a separate definition for each of those types.

What is a Typeclass in Haskell?

What's a typeclass in Haskell? A typeclass defines a set of methods that is shared across multiple types. For a type to belong to a typeclass, it needs to implement the methods of that typeclass. These implementations are ad-hoc: methods can have different implementations for different types.

What is the difference between ad hoc and universal polymorphism?

Universal or parametric polymorphism is another type of polymorphism. Unlike ad hoc, which is based on type, universal polymorphism is type-agnostic. Ad hoc polymorphism is derived from the loose translation of “ad hoc,” which is “for this.” That means the polymorphism relates specifically to certain data types.

What are overloaded types in Haskell?

A symbol is overloaded if it has two (or more) meanings, distinguished by type, that are resolved at compile time. For example, in Haskell, as in many other languages, the operator + has (at least) two distinct implementations associated with it, one of type Int -> Int -> Int, the other of type Float -> Float -> Float.


2 Answers

Well co-tuples are properly called coproducts which is just Either.

So, let's go ahead and do something like

{-# LANGUAGE TypeOperators #-}

type (+) = Either

This is left associative by the way. Now we have pretty syntax like

foo :: Int + Bool + Char
foo = Right 'c'

Now, what you seem to want there is in fact very similar to a church representation of Either flattened out. We can just build this up with the either combinator

(+) :: (a -> c)  -> (b -> c)  -> (a + b) -> c
l + r = either l r

(<+>) :: (a -> c) -> (b -> d) -> (a + b) -> (c + d)
l <+> r = either (Left . l) (Right . r)

infixl 4 <+>, +

A fun challenge would be to create a generic inject function which takes something like Proxy k where k is some representation of natural numbers at the type level and returns a great nested mess of Eithers for you.

Update:

I got bored, here's the code for generic inj

data Nat = S Nat | Z

type NatRep (n :: Nat) = Proxy n

type family Tuplish (l :: Nat) (r :: Nat) t
type instance Tuplish Z Z t     = t
type instance Tuplish (S n) Z t = (Tuplish n Z ()) + t
type instance Tuplish l (S n) t = (Tuplish l n t)  + ()

predP :: Proxy (S n) -> Proxy n
predP = reproxy

class Inject (l :: Nat) (r :: Nat) v where
  inj :: NatRep l -> NatRep r -> v  -> Tuplish l r v
instance Inject Z Z v where
  inj _ _ = id
instance Inject (S n) Z v where
  inj _ _ v = Right v
instance Inject n m v => Inject n (S m) v where
  inj l r v = Left (inj l (predP r) v)
like image 125
Daniel Gratzer Avatar answered Oct 04 '22 16:10

Daniel Gratzer


I renamed your + to >+< and your <+> to >*<, but you could do something like this:

type a + b = Either a b

(>+<) :: (a -> c) -> (b -> c) -> a + b -> c
(>+<) = either

(>*<) :: (a -> e) -> (b -> f) -> a + b -> e + f
(f >*< _) (Left  a) = Left  (f a)
(_ >*< g) (Right b) = Right (g b)

I tried to name the operators to be more suggestive of their operation.

Here's another way to implement >*<:

import Control.Arrow ((+++))

(>*<) :: (a -> e) -> (b -> f) -> a + b -> e + f
(>*<) = (+++)

As a side note: "Tuples" are often called product types and this is what's called a coproduct type (or sum type). The most basic coproduct type is Either and all other coproduct types are isomorphic to Either A B for some types A and B.

like image 36
David Young Avatar answered Oct 04 '22 15:10

David Young