4

The current curry function takes a function accepting a tuple of 2 elements and allows the resulting function to be curried or partially applied.

let x = curry (\(x, y) -> x + y)
x 1 2 -- 3

Is it possible to create a curry function that can deal with functions that have N elements in their tuples?

I tried creating it, but I'm not sure about 1: type signature, and 2: how to reverse the parameters.

curryN f 0 = f
curryN f n = \a -> (curryN (f) (n-1)) a

curryN (\(x, y, z) -> x + y + z) 3
-- I assume it looks something like: \a -> (\a -> (\a -> (f) a) a) a but I'm not sure

OR

curryN f 0 =  f
curryN f n = curryN (\a - > f a) (n -1)

On a side note, can such a function then discover the number of elements rather than needing to be told what the number is?

CMCDragonkai
  • 6,222
  • 12
  • 56
  • 98
  • 7
    If `n` is statically known, (e.g. with a proxy or type-level numeral) this is a nice exercise for type families. See e.g. [Uncurry for n-ary functions](http://stackoverflow.com/questions/24843224/uncurry-for-n-ary-functions). Using nested pairs instead of n-tuples should allow for a recursive solution. – chi Mar 05 '15 at 14:11
  • Not in standard Haskell (e.g. Haskell 98 or Haskell 2010). – n. m. could be an AI Mar 05 '15 at 17:51
  • Related: https://ro-che.info/articles/2013-01-29-generic-uncurry – Roman Cheplyaka Mar 05 '15 at 19:34
  • 2
    @chi's comment basically answers this question. To un-jargon it a little bit, the problem is that the second argument to `curryN` is not a value-level number (`2 :: Int`) but a *type-level* number. (The distinction is a little bit like that between run-time and compile-time.) Writing `curryN` therefore requires advanced type system features. For a different, practical solution, see the answer to [this question](http://stackoverflow.com/questions/7220953/does-haskell-have-variadic-functions-tuples). – Christian Conkle Mar 05 '15 at 20:46
  • Thanks for the pointers, although I would appreciate if you could post an answer so I can accept an answer to this question. Would be great for an answer to show different ways of achieving this, including the practical way @ChristianConkle and the type family way. – CMCDragonkai Mar 06 '15 at 02:42
  • I think this question is a duplicate either way. @chi is one of the answerers on the n-ary question; if you want some further explanation, you could leave a comment there. It might make sense to edit "currying" into the title of the question I linked. – Christian Conkle Mar 06 '15 at 19:13

1 Answers1

4

One of the ways to implement such function is to use GHC.Generics. With this approach we don't even need to pass a number of parameters (or tuple size). This works because there is an instance of Generic defined for tuples which effectively converts a tuple into tree structure (of type Rep a) which we can then traverse from right to left (using continuation passing style here) generating curried function along the way and packing the values of those parameters into identical Rep a structure which then converted into tuple with to function and passed to the original un-curried function-parameter. This code uses only type-level tree of parameters (from function is not used) since we produce the tuple rather then receiving it. The only limitation of this approach is that Generic is defined only for up to eight-element tuple.

{-# LANGUAGE TypeOperators, MultiParamTypeClasses,
  FlexibleInstances, UndecidableInstances,
  TypeFamilies, ScopedTypeVariables #-}

import GHC.Generics


-- | class for `curryN` function
class CurryN t r where
    type CurriedN t r :: *
    curryN :: (t -> r) -> CurriedN t r

-- | Implementation of curryN which uses GHC.Generics
instance (Generic t, GCurryN (Rep t) r) => CurryN t r where
    type CurriedN t r = GCurriedN (Rep t) r
    curryN f = gcurryN (f . to)

-- | Auxiliary class for generic implementation of `curryN`
--   Generic representation of a tuple is a tree of its elements
--   wrapped into tuple constructor representation
--   We need to fold this tree constructing a curried function
--   with parameters corresponding to every elements of the tuple
class GCurryN f r where
    type GCurriedN f r :: *
    gcurryN :: (f p -> r) -> GCurriedN f r

-- | This matches tuple definition
--   Here we extract tree of tuple parameters and use other instances to "fold" it into function
instance (GCurryN f r) => GCurryN (D1 e1 (C1 e2 f)) r where
    type GCurriedN (D1 e1 (C1 e2 f)) r = GCurriedN f r
    gcurryN c = gcurryN (\t -> c (M1 (M1 t)))

-- | A node of the tree (combines at least two parameters of the tuple)
instance (GCurryN b r, GCurryN a (GCurriedN b r)) => GCurryN (a :*: b) r where
    type GCurriedN (a :*: b) r = GCurriedN a (GCurriedN b r)
    gcurryN c = gcurryN (\a -> gcurryN (\b -> c (a :*: b)))

-- | A leaf of the tree (a single tuple parameter)
instance GCurryN (S1 NoSelector (Rec0 a)) r where
    type GCurriedN (S1 NoSelector (Rec0 a)) r = a -> r
    gcurryN c = \a -> c $ M1 (K1 a)


-- Examples of usage
t2 = curryN (uncurry (&&))

t3 = curryN (\(a,b,c) -> a + b + c)

t4 = curryN (\(a,b,c,d) -> ((a , b) , (c , d)))

tf = curryN (\(f,a,xs) -> foldr f a xs)

t5 = curryN (\(a,b,c,d,e) -> (a ++ b , c - d, not e))

t7 = curryN (\(a1,a2,a3,a4,a5,a6,a7) -> a7)
Ed'ka
  • 6,595
  • 29
  • 30