Polyvariadic functions and keyword arguments: pattern-matching on the type of the context


 

Introduction

At first sight, functions with the variable number of arguments of different types appear impossible to define in a typed language, without resorting to dependent types. In reality, we only need polymorphism. The simplest polymorphic function, the identity, is already polyvariadic:

     id id id id id True
     -- True
     id (\k -> k 1) (\v k -> k (v,True)) (\v k -> k (v,"str")) id
     -- ((1,True),"str")
     
     let go = flip ($)
         begin = go ()
         push x s = go (x,s)
         add (x,(y,s)) = go (x+y,s)
         mul (x,(y,s)) = go (x*y,s)
     in begin (push 1) (push 2) (push 3) mul (push 4) add add id
     -- (11,())

The trick is to arrange for the return type of the function to be a type variable. It can always be instantiated to an arrow type, letting the function accept one more argument. Functions in the continuation-passing style are naturally polymorphic in the return, that is, the answer-type. Danvy's Functional Unparsing is the clearest demonstration of the technique.

On this page we collect more elaborate applications. The key idea is that the concrete type of a polymorphic term is determined by the context into which the term is placed. Pattern-matching on that concrete type lets the term determine the context of its use: specifically, the term can determine the number and the types of the values it receives as arguments, and what is expected in return. The term uses that information to chose the appropriate operation. For example, given

     class C a where
         f :: String -> a
the term f "Hello, " has the polymorphic type C a => a. If the term appears in the context
     putStrLn $ f "Hello, " True " world" '!'
the type variable a is instantiated to the concrete type Bool -> String -> Char -> String. Hopefully, there is an instance of C with this type, defining the required operation. Such instances can be built inductively:
     instance C x => C (Char -> x) where
         f a x = f (a ++ [x])
     
     instance C x => C (Bool -> x) where
         f a x = f (a ++ show x)
     
     instance C x => C (String -> x) where
         f a x = f (a ++ x)

The class C lets the term f pattern-match on its continuation. The class is the template for most of the code on this page. The pattern-matching will be more elaborate. For example, the arguments do not have to be processed in the order they are received: the term can rearrange its arguments into some canonical order before performing the requested operation. That is the idea behind the implementation of keyword arguments.

 

Functions with the variable number of (variously typed) arguments

It is sometimes claimed that Haskell does not have polyvariadic functions. Here we demonstrate how to define functions with indefinitely many arguments; those arguments do not have to be of the same type.

The code referenced below shows that defining polyvariadic functions takes only a few lines of Haskell code, and requires only the most common extension of multiparameter classes with functional dependencies. Here is an example of using a polyvariadic function, build, which takes an arbitrary number of arguments and returns them in a list. The function build is first class, and so can be passed as an argument to other functions, such as use_build below.

     use_build::(forall r a. (BuildList a r) => a -> r) 
                -> x -> x -> x -> x -> [[x]]
     use_build bb a b c d =
       let t1 = bb a                -- bb is indeed polyvariadic
           t2 = bb a b
           t3 = bb a b c
           t4 = bb a b c d
           t5 = bb a b c d a
      in [t1,t2,t3,t4,t5]
     test_ub = use_build build 'a' 'b' 'c' 'd'
       -- result: ["a","ab","abc","abcd","abcda"]

The source code accompanying the HList paper ``Strongly typed heterogeneous collections'' demonstrates a similar polyvariadic function hBuild to make heterogeneous lists and records. Not only hBuild has a variable number of arguments, those arguments may all have different types.

Version
The current version is 1.1, June 2004.
References

Literate Haskell code [plain text file]
The complete description of the technique, the explanation of the type inference for functions with the variable number of arguments, and many examples.
The code and the explanations were posted in a series of messages Re: how to write a list builder? fixpoint? on Haskell and Haskell-Cafe mailing lists on June 1 - 8, 2004.

Strongly typed heterogeneous collections

Polyvariadic composition

A polyvariadic function of a non-regular type (Int->)n([]ne)->...

Lambda abstractions in C++ vs. Scheme. Currying
Unexpectedly, the Haskell realization of functions with the unlimited number of variously typed arguments turns out almost identical to the implementation of ``currying'' in C++, developed five years prior.

 

A polyvariadic function of a non-regular type (Int->)n([]ne)->...

This code implements a function for replacing an element in a multi-dimensional list. The function is overloaded to handle lists of any dimensions, and so has the variable number of index arguments specifying the location of the element to replace. The number of index arguments, of the type Int, must match the dimensionality of the list. In other words, the desired function has all of the following signatures all at the same time.

     replace :: e -> e -> e             -- replacing in a 0-dim list
     replace :: Int -> [e] -> e -> [e]
     replace :: Int -> Int -> [[e]] -> e -> [[e]]
     replace :: Int -> Int -> Int -> [[[e]]] -> e -> [[[e]]]
     ...
Here e is the type of list elements; the function returns the updated list. For example, replace (2::Int) (1::Int) strs 'X' takes the list of strings and replaces the second character of the third string with the 'X'.

The gist of the solution is the case analysis of the type of function's continuation. Or: bottom-up deterministic parsing of the type of the continuation.

This problem was posed as a `Type class puzzle' by Yitzchak Gale on the Haskell-Cafe mailing list in Oct 2006. As a matter of fact, Yitzchak Gale asked for a function with a slightly different signature, with the different order of the last two arguments, e.g., replace :: Int -> Int -> e -> [[e]] -> [[e]], etc. If we consider the set of the signatures as a language, we notice the problem: its LALR-like grammar has a shift/reduce conflict. Indeed, the type of list elements may itself be Int. Thus, after scanning two Int arguments and looking ahead at another Int, we cannot tell if we are dealing with the replacement in a 2D Int list, or the replacement in a higher-dimensional non-Int list. This problem in the grammar would compel the use of overlapping instances and other typeclass tricks. Since the order of replace's last two arguments seems to have been chosen quite arbitrarily by the original poster, it makes sense for us to pick the order that leads to a LALR(1) language and the simple solution, with no need for overlapping instances.

This puzzle demonstrates the benefits of bringing the tools from quite a different area of computer science -- parsing and grammars -- to seemingly unrelated type class programming. Types and parsing are, of course, deeply related: cf. type logical grammars.

The implementations of replace and the explanation of the parsing problem and the solutions have been written by Chung-chieh Shan.

Version
The current version is 1.1, Nov 12, 2006.
References

<http://www.haskell.org/pipermail/haskell-cafe/2006-November/019475.html>
A message by Chung-chieh Shan with the detailed explanation of the problem with the original puzzle. The message describes two solutions. The message was posted as Re: A type class puzzle on the Haskell-Cafe mailing list on Sun Nov 12 18:38:05 EST 2006.

puzzle.hs [3K]
The first, direct-style solution and tests. It is written by Chung-chieh Shan.

puzzle-cps.hs [3K]
Another, continuation-passing-style solution and tests. It is written by Chung-chieh Shan.

 

Genuine keyword arguments

We show the Haskell implementation of keyword arguments, which goes well beyond records (e.g., in permitting the re-use of labels). Keyword arguments indeed look just like regular, positional arguments. However, keyword arguments may appear in any order. Furthermore, one may associate defaults with some keywords; the corresponding arguments may then be omitted. It is a type error to omit a required keyword argument. The latter property is in stark contrast with the conventional way of emulating keyword arguments via records. Also in marked contrast with records, keyword labels may be reused throughout the code with no restriction; the same label may be associated with arguments of different types in different functions. Labels of Haskell records may not be re-used. Our solution is essentially equivalent to keyword arguments of DSSSL Scheme or labels of OCaml.

Here's one example: assigning a name to a partially applied keyword argument function without defaults:

     tests3 = let f x = kw make_square HNil Color Red x
              in f Origin (0::Int,10::Int) Size (1::Int) 

The following example illustrates defaults, to be used for omitted keyword arguments:

     tests4 = let defaults = Origin .*. (0::Int,10::Int) .*.
                             RaisedBorder .*. True .*. HNil
              in kw make_square defaults Size (1::Int) Color (RGBColor 0 10 255)

The gist of our implementation is a type-level reflection of a function.

Our solution requires no special extensions to Haskell and works with the existing Haskell compilers; it is tested on GHC 6.0.1 and 6.2.1. The overlapping instances extension is not necessary (albeit it is convenient).

Version
The current version is 1.1, August 2004.
References

Literate Haskell code [plain text file]
The complete description of the technique, and examples.
The code and the explanations were posted in a message Keyword arguments on a Haskell mailing list on Fri, 13 Aug 2004 14:58:34 -0700.

Strongly typed heterogeneous collections
The keyword argument code depends on the HList library, which implements strongly-typed polymorphic open records. In fact, the keyword argument code is included as one of the examples in the HList library.

Functions with the variable number of (variously typed) arguments

Macros with keyword (labeled) arguments
Another example of using the ``compile-time'' reflection to implement keyword arguments. Keyword resolution and argument re-ordering are done at macro-expand time.

 

Type-indexed arguments

Andrew U. Frank, in a message posted on Haskell-Cafe on Sep 10, 2009, posed a problem of generic transformations on a type-indexed collection (TIP). TIP is a heterogeneous array whose elements have distinct types. Therefore, an element can be located based solely on its type. We would like to apply to a TIP a transformation function, whose argument types and the result type are all in the TIP. The function should locate its arguments based on their types, and update the TIP with the result. The function may have any number of arguments, including zero; the order of arguments should not matter. The problem is a variation of the keyword argument problem, where the `keyword' is the argument type. Here is a simple illustration.

     newtype MyVal = MyVal Int deriving Show
     
     -- A sample TIP
     tip1 = MyVal 20 .*. (1::Int) .*. True .*. emptyTIP
     -- TIP (HCons (MyVal 20) (HCons 1 (HCons True HNil)))
     
     -- Update the Int component of tip1 to 2. The Int component must
     -- exist. Otherwise, it is a type error
     tip2 = ttip (2::Int) tip1
     -- TIP (HCons (MyVal 20) (HCons 2 (HCons True HNil)))
     
     -- Negate the boolean component of tip1
     tip3 = ttip not tip1
     -- TIP (HCons (MyVal 20) (HCons 1 (HCons False HNil)))
     
     -- Update the Int component from the values of two other components
     tip4 = ttip (\(MyVal x) y -> x+y) tip1
     -- TIP (HCons (MyVal 20) (HCons 21 (HCons True HNil)))
     
     -- Update the MyVal component from the values of three other components
     tip5 = ttip (\b (MyVal x) y -> MyVal $ if b then x+y else 0) tip1
     -- TIP (HCons (MyVal 21) (HCons 1 (HCons True HNil)))
     
     -- The same but with the permuted argument order.
     -- The order of arguments is immaterial: the values will be looked up using
     -- their types
     tip5' = ttip (\b y (MyVal x)-> MyVal $ if b then x+y else 0) tip1
     -- TIP (HCons (MyVal 21) (HCons 1 (HCons True HNil)))
Version
The current version is 1.1, Sep 15, 2009.
References

TIPTransform.hs [3K]
Commented Haskell code with the complete implementation. It was posted as Re: retrieving arguments for functions from a heterogenous list on the Haskell-Cafe mailing list on Tue, 15 Sep 2009 23:58:39 -0700 (PDT)

Strongly typed heterogeneous collections
The HList paper describes type-indexed products (TIP) in Section 7. The TIPTransform code is included as an example in the HList distribution.

 

Categorical products in Haskell

An attempt to implement the following categorical formulas in Haskell:

     max3 = max2 . (max2 * id)
     max4 = max2 . (max2 * max2)
     max5 = max2 . ((max2 * id) . (max2 * max2))
     max7 = max3 . ((max2 * max3) * max2)
where * is a categorical product and . is a categorical composition. We show the code for the product and the composition that lets us write the above formulas in Haskell as they are.

A potentially useful side-effect is an automatic deep uncurrying of arbitrarily complex pairs, such as ((1,2),(3,(4,5)))

Version
The current version is 1.8, Apr 30, 2003.
References

Literate Haskell code [plain text file]
The complete description and the implementation. It was posted as Deeply uncurried products, as categorists might like them on the Haskell mailing list on Apr 30, 2003.

An older approach [plain text file]
It was originally posted as Re: On products and max3 on the newsgroup comp.lang.functional on Thu, 12 Apr 2001 02:14:27 +0000

 

Polyvariadic composition

This article describes a combinator mcomp that does the farthest composition of functions:

     f:: a1->a2-> .... ->cp
     g:: cp->d
     f `mcomp` g:: a1->a2-> .... ->d
We resolve the ambiguity in the above definition by assuming that cp is not a functional type.

The problem was originally posed on comp.lang.functional by Immanuel Litzroth, who wrote:

The problem arose quite naturally when I was working on something todo with partial order
     PO:: A -> B -> Maybe Ordering
and now I wanted groupBy (isJust . PO)
Version
The current version is 1.1, Oct 31, 2002.
References

polyvar-comp.lhs [3K]
The literate Haskell source code and a few tests
The code was originally posted as Re: composition on a newsgroup comp.lang.functional on Wed, 30 Oct 2002 19:09:32 -0800

Categorical products in Haskell
Another application of the combinator mcomp



Last updated October 4, 2009

This site's top page is http://okmij.org/ftp/

oleg-at-pobox.com or oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!

Converted from SXML by SXML->HTML