title: Currying Product Types
body: <p>Using type families, we can define the function <em>fold</em> over a type and the underlying algebra for that type represented as an <em>n</em>-tuple of functions and constant values. This permits the definition of a generalized <em>foldr</em> function, defined in the <em>Foldable</em> type class:</p>
  
  <pre><code>import Data.Set (Set)
  import Data.Map (Map)
  import qualified Data.Set as S
  import qualified Data.Map as M
  
  class Foldable m where
    type Algebra m b :: *
    fold :: Algebra m b -&gt; m -&gt; b
  
  instance (Ord a) =&gt; Foldable (Set a) where
    type Algebra (Set a) b = (b, a -&gt; b -&gt; b)
    fold = uncurry $ flip S.fold
  
  instance (Ord k) =&gt; Foldable (Map k a) where
    type Algebra (Map k a) b = (b, k -&gt; a -&gt; b -&gt; b)
    fold = uncurry $ flip M.foldWithKey
  </code></pre>
  
  <p>Similarly, constraint kinds permit the definition of a generalized <em>map</em> function. The <em>map</em> function differs from <em>fmap</em> by considering each value field of an algebraic data type:</p>
  
  <pre><code>class Mappable m where
    type Contains m     :: *
    type Mapped   m r b :: Constraint
    map :: (Mapped m r b) =&gt; (Contains m -&gt; b) -&gt; m -&gt; r
  
  instance (Ord a) =&gt; Mappable (Set a) where
    type Contains (Set a)     = a
    type Mapped   (Set a) r b = (Ord b, r ~ Set b)
    map = S.map
  
  instance (Ord k) =&gt; Mappable (Map k a) where
    type Contains (Map k a)     = (k, a)
    type Mapped   (Map k a) r b = (Ord k, r ~ Map k b)
    map = M.mapWithKey . curry
  </code></pre>
  
  <p>From the user's perspective, neither function is particularly friendly. In particular, neither technique permits the definition of <em>curried</em> functions. This means that the user cannot easily apply either <em>fold</em> or the <em>mapped</em> function partially. What <em>I</em> would like is a type-level function that curries tuples of functions and values, in order to generate curried versions of the above. Thus, I would like to write something approximating the following type-function:</p>
  
  <pre><code>Curry :: Product -&gt; Type -&gt; Type
  Curry ()       m = m
  Curry (a × as) m = a -&gt; (Curry as m b)
  </code></pre>
  
  <p>If so, we could generate a curried fold function from the underlying algebra. For instance:</p>
  
  <pre><code>  fold :: Curry (Algebra [a] b) ([a] -&gt; b)
  ≡ fold :: Curry (b, a -&gt; b -&gt; b) ([a] -&gt; b)
  ≡ fold :: b -&gt; (Curry (a -&gt; b -&gt; b)) ([a] -&gt; b)
  ≡ fold :: b -&gt; (a -&gt; b -&gt; b -&gt; (Curry () ([a] -&gt; b))
  ≡ fold :: b -&gt; ((a -&gt; b -&gt; b) -&gt; ([a] -&gt; b))
  
    map :: (Mapped (Map k a) r b) =&gt; (Curry (Contains (Map k a)) b) -&gt; Map k a -&gt; r
  ≡ map :: (Mapped (Map k a) r b) =&gt; (Curry (k, a) b) -&gt; Map k a -&gt; r
  ≡ map :: (Mapped (Map k a) r b) =&gt; (k -&gt; (Curry (a) b) -&gt; Map k a -&gt; r
  ≡ map :: (Mapped (Map k a) r b) =&gt; (k -&gt; (a -&gt; Curry () b)) -&gt; Map k a -&gt; r
  ≡ map :: (Mapped (Map k a) r b) =&gt; (k -&gt; (a -&gt; b)) -&gt; Map k a -&gt; r
  </code></pre>
  
  <p>I know that Haskell doesn't have type functions, and the proper representation of the <em>n</em>-tuple would probably be something like a type-level length-indexed list of types. Is this possible?</p>
  
  <p><strong>EDIT:</strong> For completeness, my current attempt at a solution is attached below. I am using empty data types to represent products of types, and type families to represent the function <em>Curry</em>, above. This solution appears to work for the <em>map</em> function, but not the <em>fold</em> function. I <em>believe</em>, but am not certain, that <em>Curry</em> is not being reduced properly when type checking.</p>
  
  <pre><code>data Unit
  data Times a b
  
  type family Curry a m :: *
  type instance Curry Unit        m = m
  type instance Curry (Times a l) m = a -&gt; Curry l m
  
  class Foldable m where
    type Algebra m b :: *
    fold :: Curry (Algebra m b) (m -&gt; b)
  
  instance (Ord a) =&gt; Foldable (Set a) where
    type Algebra (Set a) b = Times (a -&gt; b -&gt; b) (Times b Unit)
    fold = S.fold
  
  instance (Ord k) =&gt; Foldable (Map k a) where
    type Algebra (Map k a) b = Times (k -&gt; a -&gt; b -&gt; b) (Times b Unit)
    fold = M.foldWithKey
  
   class Mappable m where
     type Contains m     :: *
     type Mapped   m r b :: Constraint
     map :: (Mapped m r b) =&gt; Curry (Contains m) b -&gt; m -&gt; r
  
   instance (Ord a) =&gt; Mappable (Set a) where
     type Contains (Set a)     = Times a Unit
     type Mapped   (Set a) r b = (Ord b, r ~ Set b)
     map = S.map
  
   instance (Ord k) =&gt; Mappable (Map k a) where
     type Contains (Map k a)     = Times k (Times a Unit)
     type Mapped   (Map k a) r b = (Ord k, r ~ Map k b)
     map = M.mapWithKey
  </code></pre>