Frown is an LALR(k) parser generator for Haskell 98 written in Haskell 98. Its salient features are: • The generated parsers are time and space efficient. On the downside, the parsers are quite...
We introduce 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the...
J. Van Leeuwen, Jeremy Gibbons, Ralf Hinze, Johan Jeuring (eds
A leitmotif in the evolution of programming paradigms has been the level and extent of parametrisation that is facilitated — the so-called genericity of the paradigm. The sorts of parameters that...
ÓÔ�Ö�Ø�ÓÒ �ÓÖ ��Ð�Ñ�Ø�Ò � Ø� � �« � Ø Ó � � ÙØ �Ö � ×ÙÔÔÓÖØ�� (2008)
� �ÈÖÓ�Ö�ÑÑ�Ò � Ä�Ò�Ù���×℄ � Ä�Ò�Ù�� � �ÓÒ×ØÖÙ Ø×
ABSTRACT A Simple Implementation Technique for Priority Search Queues (2008)
This paper presents a new implementation technique for priority search queues. This abstract data type is an amazing blend of finite maps and priority queues. Our implementation supports logarithmic...
Datatype-Generic Programming 2006 (2008)
Ralf Hinze, Johan Jeuring, Andres Löh, Ralf Hinze, Johan Jeuring, Andres Löh
www.cs.uu.nl
Chapter 2 Comparing Approaches to Generic Programming in Haskell (2008)
Ralf Hinze, Johan Jeuring, Andres Löh
Abstract. The last decade has seen a number of approaches to datatype-generic programming: PolyP, Functorial ML, ‘Scrap Your Boilerplate’, Generic Haskell, ‘Generics for the Masses’, and so...
Under consideration for publication in J. Functional Programming 1 Generics for the masses (2008)
A generic function is a function that can be instantiated on many data types to obtain data type specific functionality. Examples of generic functions are the functions that can be derived in...
Haskell (Peyton Jones, 2003) is often used as a host for another language. Typically, the abstract syntax of the guest language is defined by a bunch of data type declarations; parsers and...
We introduce 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the...
Categories and Subject Descriptors (2008)
The abstract data type one-sided flexible array, also called randomaccess list, supports look-up and update of elements and can grow and shrink at one end. We describe a purely functional...
Generics as a Library (Extended Abstract) (2008)
Typically, a generic function is a function that is defined on the structure of data types: with a single definition, we obtain a function that works for many data types. In contrast, an ad-hoc...
Under consideration for publication in J. Functional Programming 1 Manufacturing Datatypes (2008)
This article describes a general framework for designing purely functional datatypes that automatically satisfy given size or structural constraints. Using the framework we develop implementations of...
The Generic H A SKELL Team (2008)
Andres Löh, Johan Jeuring, Thomas Van Noort, Alexey Rodriguez, Dave Clarke, Ralf Hinze, ...
www.cs.uu.nl
Dæv Clarke, Ralf Hinze, Johan Jeuring, Andres Löh, Skell Team
1.1 Generic programming............................. 4
(e-mail: johanjcs.uu.nl) Just a little bit of it can bring you up and down.-- Genesis, it 1
1 A Simple Implementation Technique for Priority Search Queues (2007)
This paper presents a new implementation technique for priority search queues. This abstract data type is an amazing blend of nite maps and priority queues. Our implementation supports logarithmic...
A polytypic function is a function that can be instantiated on many data types to obtain data type specic functionality. Examples of polytypic functions are the functions that can be derived in...
Introduction Suppose, you want to implement a structured editor for some term type, so that the user can navigate through a given term and perform edit actions on subterms. In this case you are...
Under consideration for publication in J. Functional Programming 1 FUNCT I ONAL PEARL (2007)
Fresh Look At, Ralf Hinze, Oswald Spengler
Introduction Binary search trees are old hat, aren't they? Search trees are routinely covered in introductory computer science classes and they are widely used in functional programming courses...
International Journal of Foundations of Computer Science (2007)
World Scienti Publishing, Ralf Hinze
The purpose of this article is twofold. First, we show that Prolog's control constructs can be smoothly integrated into a functional language like Haskell. The resulting `language', termed...
Under consideration for publication in J. Functional Programming 1 FUNCT I ONAL PEARL (2007)
Formatting Class Act, Ralf Hinze
Introduction When I was a student, Simula was one of the languages taught in introductory programming language courses and I vividly remember a sticker one of our instructors had attached to the door...
Church Numerals, Twice! (2007)
This pearl explains Church numerals, twice. The first explanation links Church numerals to Peano numerals via the well-known encoding of data types in the polymorphic #-calculus. This view suggests...
Abstract. In this paper we discuss the surprisingly elegant interaction between two lines of rather independent research, namely generic (or polytypic) programming and dynamic types. We show how the...
Under consideration for publication in J. Functional Programming 1 FUNCT I ONAL PEARL (2007)
Introduction When I was a student, Simula was one of the languages taught in introductory programming language courses and I vividly remember a sticker one of our instructors had attached to the door...
Scrap your boilerplate” reloaded (2006)
Abstract. The paper “Scrap your boilerplate ” (SYB) introduces a combinator library for generic programming that offers generic traversals and queries. Classically, support for generic...
Scrap your boilerplate” reloaded (2006)
Abstract. The paper “Scrap your boilerplate ” (SYB) introduces a combinator library for generic programming that offers generic traversals and queries. Classically, support for generic...
Haskell Communities and Activities Report (2006)
Andres Löh (ed, Lloyd Allison, Tiago Miguel, Laureano Alves, Krasimir Angelov, Dmitry Astapov, ...
Welcome to the eleventh edition of the Haskell Communities and Activities Report – a collection of entries about everything that is going on and related to Haskell in some way that appears twice a...
Scrap your boilerplate” revolutions (2006)
Abstract. Generic programming allows you to write a function once, and use it many times at different types. Traditionally, generic functions are defined by induction on the structure of types....
Haskell Communities and Activities Report (2006)
Andres Löh (ed, Lloyd Allison, Tiago Miguel, Laureano Alves, Krasimir Angelov, Dmitry Astapov, ...
This is the tenth edition of the Haskell Communities and Activities Report (HCAR) – a collection of entries about everything that is going on and related to Haskell in some way that appears twice a...
Generic programming, now (2006)
Abstract. Tired of writing boilerplate code? Tired of repeating essentially the same function definition for lots of different datatypes? Datatype-generic programming promises to end these coding...
A generic function is a function that is defined on the structure of data types: with a single definition, we obtain a function that works for many data types. In contrast, an ad-hoc polymorphic...
Typed contracts for functional programming (2006)
Ralf Hinze, Johan Jeuring, Andres Löh
Abstract. A robust software component fulfills a contract: it expects data satisfying a certain property and promises to return data satisfying another property. The object-oriented community uses...
A generic function is a function that is defined on the structure of data types: with a single definition, we obtain a function that works for many data types. In contrast, an ad-hoc polymorphic...
Scrap your boilerplate” revolutions (2006)
Abstract. Generic programming allows you to write a function once, and use it many times at different types. Traditionally, generic functions are defined by induction on the structure of types....
Scrap your boilerplate” reloaded (2006)
Abstract. The paper “Scrap your boilerplate ” (SYB) introduces a combinator library for generic programming that offers generic traversals and queries. Classically, support for generic...
Comparing approaches to generic programming in Haskell (2006)
Ralf Hinze, Johan Jeuring, Andres Löh
Abstract. The last decade has seen a number of approaches to datatype-generic programming: PolyP, Functorial ML, ‘Scrap Your Boilerplate’, Generic Haskell, ‘Generics for the Masses’, etc. The...
The Generic H A SKELL Team (2006)
Andres Löh, Johan Jeuring, Alexey Rodriguez (editors, Andres Löh (editor, Johan Jeuring (editor, Alexey Rodriguez (editor, ...
www.cs.uu.nl
Typed contracts for functional programming (2006)
Ralf Hinze, Ralf Hinze, Johan Jeuring, Johan Jeuring, Andres Löh, Andres Löh
Abstract. A robust software component fulfills a contract: it expects data satisfying a certain property and promises to return data satisfying another property. The object-oriented community uses...
The Generic Haskell User's Guide - Version 1.42 - Coral release (2005)
Andres Löh, Johan Jeuring, Andres Löh (editor, Johan Jeuring (editor, Dave Clarke, Jan De Wit, ...
Contents SKELL? 5 1.1 Generic programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 SKELL overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Installation 6 2.1...
"Scrap Your Boilerplate" Explained (2005)
The paper "Scrap your Boilerplate" (SYB) introduces a combinator library for generic programming that o#ers generic traversals and queries. Classically, support for generic programming...
Haskell Communities and Activities Report (2005)
Andres Löh (ed, Lloyd Allison, Tiago Miguel, Laureano Alves, Krasimir Angelov, Alistair Bayley, ...
Finally, here is the 9th edition of the Haskell Communities and Activities Report (HCAR), almost three weeks after the submission deadline. This delay is entirely my own fault. In fact, I have to...
Abstract. A parallel prefix circuit takes n inputs x1, x2,..., xn and produces the n outputs x1, x1 ◦ x2,..., x1 ◦ x2 ◦ · · · ◦ xn, where ‘◦ ’ is an arbitrary associative binary...
First-Class Phantom Types (2003)
Classical phantom types are datatypes in which type constraints are expressed using type variables that do not appear in the datatype cases themselves. They can be used to embed typed languages into...
First-Class Phantom Types (2003)
Classical phantom types are datatypes in which type constraints are expressed using type variables that do not appear in the datatype cases themselves. They can be used to embed typed languages into...
Generic Haskell: applications (2003)
Abstract. Generic Haskell is an extension of Haskell that supports the construction of generic programs. These lecture notes discuss three advanced generic programming applications: generic...
Derivation of a typed functional LR parser (2003)
Abstract. This paper describes a purely functional implementation of LR parsing. We formally derive our parsers in a series of steps starting from the inverse of printing. In contrast to traditional...
Phantom types are data types with type constraints associated with dierent cases. Examples of phantom types include typed type representations and typed higher-order abstract syntax trees. These...
Generic Haskell: Applications (2003)
Generic Haskell is an extension of Haskell that supports the construction of generic programs. This article describes generic programming in practice. It discusses three advanced generic programming...
First-class phantom types (2003)
Abstract. Phantom types are data types with type constraints associated with different cases. Examples of phantom types include typed type representations and typed higher-order abstract syntax...
Generic Haskell: practice and theory (2003)
Abstract. Generic Haskell is an extension of Haskell that supports the construction of generic programs. These lecture notes describe the basic constructs of Generic Haskell and highlight the...
Generic Haskell: Practice and Theory (2003)
Generic Haskell is an extension of Haskell that supports the construction of generic programs. These lecture notes describe the basic constructs of Generic Haskell and highlight the underlying theory.
Generic Haskell: Practice and Theory (2003)
Generic Haskell is an extension of Haskell that supports the construction of generic programs. This article describes the basics of Generic Haskell and highlights the underlying theory.
The Generic HASKELL Users Guide (2002)
Clarke, Dæv, Hinze, Ralf, Jeuring, Johan Theodoor, Löh, Andres, Wit, Jan De
Type-indexed data types (2002)
A polytypic function is a function that can be instantiated on many data types to obtain data type specific functionality. Examples of polytypic functions are the functions that can be derived in...
Type-indexed data types (2002)
Abstract. A polytypic function is a function that can be instantiated on many data types to obtain data type specic functionality. Examples of polytypic functions are the functions that can be...
Type-indexed data types (2002)
Ralf Hinze, Johan Jeuring, Andres Löh
Abstract. A polytypic function is a function that can be instantiated on many data types to obtain data type specific functionality. Examples of polytypic functions are the functions that can be...
A Lightweight Implementation of Generics and Dynamics (2002)
The recent years have seen a number of proposals for extending statically typed languages by dynamics or generics. Most proposals --- if not all --- require significant extensions to the underlying...
Constructing tournament representations: An exercise in pointwise relational programming (2002)
Abstract. List or set comprehensions are a wonderful means to define nondeterministic or relational programs. Despite their beauty, comprehensions are somewhat underused in program calculation. The...
Bootstrapping One-sided Flexible Arrays (2002)
The abstract data type one-sided flexible array, also called randomaccess list, supports look-up and update of elements and can grow and shrink at one end. We describe a purely functional...
Constructing Tournament Representations: An exercise in pointwise relational programming (2002)
List or set comprehensions are a wonderful means to de ne nondeterministic or relational programs. Despite their beauty, comprehensions are somewhat underused in program calculation. The purpose of...
Church numerals, twice! (2002)
This paper explains Church numerals, twice. The first explanation links Church numerals to Peano numerals via the well-known encoding of data types in the polymorphic λ-calculus. This view suggests...
Countdown is a popular quiz programme on British television that includes a numbers game that we shall refer to as the countdown problem (Hutton, 2002)—this abstract is stolen from Hutton’s...
Combining Generics and Dynamics (2002)
Abstract. In this paper we discuss the surprisingly elegant interaction between two lines of rather independent research, namely generic (or polytypic) programming and dynamic types. We show how the...
A simple implementation technique for priority search queues (2001)
This paper presents a new implementation technique for priority search queues. This abstract data type is an amazing blend of finite maps and priority queues. Our implementation supports logarithmic...
A simple implementation technique for priority search queues (2001)
This paper presents a new implementation technique for priority search queues. This abstract data type is an amazing blend of finite maps and priority queues. Our implementation supports logarithmic...
The Web (Functional Pearl) (2001)
Introduction Say, you want to implement a structured editor for some term type, so that the user can navigate through a given term and perform edit actions on subterms. In this case you are...
Polytypic Values Possess Polykinded Types (2001)
A polytypic value is one that is defined by induction on the structure of types. In Haskell types are assigned so-called kinds that distinguish between manifest types like the type of integers and...
A simple implementation technique for priority search queues (2001)
This paper presents a new implementation technique for priority search queues. This abstract data type is an amazing blend of finite maps and priority queues. Our implementation supports logarithmic...
Polytypic Programming with Ease (2001)
This article proposes a new framework for a polytypic extension of functional programming languages. A polytypic functional program is one that is parameterised by datatype. Since polytypic functions...
Deriving Backtracking Monad Transformers (2000)
In a paper about pretty printing J. Hughes introduced two fundamental techniques for deriving programs from their specication, where a specication consists of a signature and properties that the...
Polytypic Values Possess Polykinded Types (2000)
A polytypic value is one that is defined by induction on the structure of types. In Haskell the type structure is described by the so-called kind system, which distinguishes between manifest types...
Polytypic Values Possess Polykinded Types (2000)
. A polytypic value is one that is dened by induction on the structure of types. In Haskell types are assigned so-called kinds that distinguish between manifest types like the type of integers and...
Ralf Hinze, Simon Peyton Jones
Generic programming allows you to write a function once, and use it many times at different types. A lot of good foundational work on generic programming has been done. The goal of this paper is to...
Ralf Hinze, Simon Peyton Jones
Generic programming allows you to write a function once, and use it many times at dierent types. A lot of good foundational work on generic programming has been done. The goal of this paper is to...
Ralf Hinze, Simon Peyton Jones
Generic programming allows you to write a function once, and use it many times at dierent types. A lot of good foundational work on generic programming has been done. The goal of this paper is to...
Memo Functions, Polytypically! (2000)
. This paper presents a polytypic implementation of memo functions that are based on digital search trees. A memo function can be seen as the composition of a tabulation function that creates a memo...
Electronic Notes in Theoretical Computer Science 41 No. 1 (2001) (2000)
Url Http Www, Ralf Hinze, Simon Peyton Jones
Generic programming allows you to write a function once, and use it many times at dierent types. A lot of good foundational work on generic programming has been done. The goal of this paper is to...
John Hughes [editor, Lennart Augustsson, Dave Barton, Brian Boutel, Warren Burton, ...
for the
Polytypic functions over nested datatypes (1999)
The theory and practice of polytypic programming is intimately connected with the initial algebra semantics of datatypes. This is both a blessing and a curse. It is a blessing because the underlying...
Polytypic Functions Over Nested Datatypes (1999)
ly speaking, mapM / f 0 defines the action on arrows in the Kleisli category induced by m. If we specialize m to Id, the identity monad, we obtain the `ordinary' map operation. Since mapM / f 0...
Polytypic Functions Over Nested Datatypes (1999)
ly speaking, mapMhf i defines the action on arrows in the Kleisli category induced by m. If we specialize m to Id, the identity monad, we obtain the `ordinary' map operation. Since mapMhf i is...
Polytypic Programming With Ease (1999)
A functional polytypic program is one that is parameterised by datatype. Since polytypic functions are defined by induction on types rather than by induction on values they typically operate on a...
Efficient Generalized Folds (1999)
Fold operators capture a common recursion pattern over algebraic datatypes. A fold essentially replaces constructors by functions. However, if the datatype is parameterized, the corresponding fold...
A New Approach to Generic Functional Programming (1999)
This paper describes a new approach to generic functional programming, which allows us to define functions generically for all datatypes expressible in Haskell. A generic function is one that is...
Straight to the Heart of Computer Science via Functional Programming (1999)
Robert Giegerich, Ralf Hinze, Stefan Kurtz
We outline a deductive concept for an introductory course to computer science aimed at CS students as well as students from other disciplines. The emphasis is on introducing fundamental concepts of...
Perfect Trees and Bit-reversal Permutations (1999)
A famous algorithm is the Fast Fourier Transform, or FFT. An efficient iterative version of the FFT algorithm performs as a first step a bit-reversal permutation of the input list. The bit-reversal...
A Generic Programming Extension for Haskell (1999)
Many functions can be dened completely generically for all datatypes. Examples include pretty printers (eg show), parsers (eg read), data converters, equality and comparison functions, mapping...
Deriving Monad Transformers (1999)
In a paper about pretty printing J. Hughes introduced two fundamental techniques for deriving programs from their specification, where a specification consists of a signature and properties that the...
A New Approach to Generic Functional Programming (1999)
This paper describes a new approach to generic functional programming, which allows us to define functions generically for all datatypes expressible in Haskell. A generic function is one that is...
Constructing Red-Black Trees (1999)
This paper explores the structure of red-black trees by solving an apparently simple problem: given an ascending sequence of elements, construct a red-black tree which contains the elements in...
Straight to the Heart of Computer Science via Functional Programming (1999)
Robert Giegerich, Ralf Hinze, Stefan Kurtz
We outline a deductive concept for an introductory course to computer science aimed at CS students as well as students from other disciplines. The emphasis is on introducing fundamental concepts of...
Polytypic Functions Over Nested Datatypes (Extended Abstract) (1999)
) Ralf Hinze Institut fur Informatik III, Universitat Bonn Romerstraße 164, 53117 Bonn, Germany (e-mail: ralf@informatik.uni-bonn.de) Abstract. The theory and practice of polytypic programming is...
Polytypic Functions Over Nested Datatypes (1999)
The theory and practice of polytypic programming is intimately connected with the initial algebra semantics of datatypes. This is both a blessing and a curse. It is a blessing because the underlying...
Constructing Red-Black Trees (1999)
This paper explores the structure of red-black trees by solving an apparently simple problem: given an ascending sequence of elements, construct, in linear time, a red-black tree that contains the...
Manufacturing Datatypes (1999)
This paper describes a general framework for designing purely functional datatypes that automatically satisfy given size or structural constraints. Using the framework we develop implementations of...
Generalizing Generalized Tries (1999)
A trie is a search tree scheme that employs the structure of search keys to organize information. Tries were originally devised as a means to represent a collection of records indexed by strings over...
Manufacturing Datatypes (1999)
This paper describes a general framework for designing purely functional datatypes that automatically satisfy given size or structural constraints. Using the framework we develop implementations of...
Functional Pearls: Explaining Binomial Heaps (1999)
This paper explains binomial heaps, a beautiful data structure for priority queues, using the functional programming language Haskell (Peterson & Hammond, 1997). We largely follow a deductive...
Report on the Programming Language (1999)
Purely Functional Language, John Hughes [editor, Lennart Augustsson, Dave Barton, ...
Perfect Trees and Bit-Reversal Permutations (1999)
Perfect Trees, Bit-reversal Permutations, Ralf Hinze
A famous algorithm is the Fast Fourier Transform, or FFT. An ecient iterative version of the FFT algorithm performs as a rst step a bit-reversal permutation of the input list. The bit-reversal...
Polytypic functions over nested datatypes (1999)
The theory and practice of polytypic programming is intimately connected with the initial algebra semantics of datatypes. This is both a blessing and a curse. It is a blessing because the underlying...
Constructing red-black trees (1999)
This paper explores the structure of red-black trees by solving an apparently simple problem: given an ascending sequence of elements, construct a red-black tree which contains the elements in...
Polytypic Functions Over Nested Datatypes (1999)
The theory and practice of polytypic programming is intimately connected with the initial algebra semantics of datatypes. This is both a blessing and a curse. It is a blessing because the underlying...
Prological Features In A Functional Setting Axioms And Implementations (1998)
this paper is twofold. First, we show that Prological features
Numerical Representations as Higher-Order Nested Datatypes (1998)
Number systems serve admirably as templates for container types: a container object of size n is modelled after the representation of the number n and operations on container objects are modelled...
Efficient monadic-style backtracking (1996)
Lists are ubiquitous in functional programming. The list constructor forms an instance of a monad capturing non-deterministic computations. Despite its popularity the list monad suffers from serious...
Projection-based strictness analysis : theoretical and practical aspects / (1995)
Bonn, Univ., Diss., 1995.
Generalizing Generalized Tries
A trie is a search tree scheme that employs the structure of search keys to organize information. Tries were originally devised as a means to represent a collection of records indexed by strings over...