(Int->)^{n}([]^{n}e)->...
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 -> athe term
f "Hello, "
has the polymorphic type
C a => a
. If the term appears in the contextputStrLn $ 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.
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.
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
A polyvariadic function of a non-regular type (Int->)^{n}([]^{n}e)->...
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.
(Int->)^{n}([]^{n}e)->...
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.
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.
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).
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.
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)))
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.
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)))
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
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-> .... ->dWe 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 orderPO:: A -> B -> Maybe Orderingand now I wantedgroupBy (isJust . PO)
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
This site's top page is http://okmij.org/ftp/
Converted from SXML by SXML->HTML