916 papers · page 13 of 46
Jesús Aransay, Jose Divasón
Abstract In this paper, we present a formalisation in a proof assistant, Isabelle/HOL, of a naive version of the Gauss-Jordan algorithm, with explicit proofs of some of its applications; and, additionally, a process to obtain versions of this algorithm in two different functional…
Robert Atkey, Patricia Johann
Abstract The study of programming with and reasoning about inductive datatypes such as lists and trees has benefited from the simple categorical principle of initial algebras. In initial algebra semantics, each inductive datatype is represented by an initial f -algebra for an app…
Patrick Bahr, Graham Hutton
Abstract In this article, we present a new approach to the problem of calculating compilers. In particular, we develop a simple but general technique that allows us to derive correct compilers from high-level semantics by systematic calculation, with all details of the implementa…
Jean-Philippe Bernardy, Koen Claessen
Abstract We present a divide-and-conquer algorithm for parsing context-free languages efficiently. Our algorithm is an instance of Valiant's (1975; General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10 (2), 308–314), who reduced the problem of parsing…
Richard S. Bird
The setting is a class on functional programming. There are four students: Anne, Jack, Mary and Theo.
Koen Claessen, Jonas Duregård, Michal H. Palka
Abstract We present a technique for automatically deriving test data generators from a given executable predicate representing the set of values we are interested in generating. The distribution of these generators is uniform over values of a given size. To make the generation ef…
Amanda Clare
Sharon A. Curtis, Shin-Cheng Mu
Abstract The problem of finding a densest segment of a list is similar to the well-known maximum segment sum problem, but its solution is surprisingly challenging. We give a general specification of such problems, and formally develop a linear-time online solution, using a slidin…
Marius Eriksen, Michael Sperber, Anil Madhavapeddy
The Commercial Users of Functional Programming workshop (CUFP) is an annual workshop held in association with the International Conference on Functional Programming (ICFP). The aim of the CUFP workshops is to publicize the use of functional programming in commercial ventures. Its…
Daniel Fridlender, Miguel Pagano
Abstract We introduce a new formulation of pure type systems (PTSs) with explicit substitution and de Bruijn indices and formally prove some of its meta-theory. Using techniques based on Normalisation by Evaluation, we prove that untyped conversion can be typed for predicative PT…
Torsten Grust
With Thinking Functionally in Haskell Richard Bird steps up to continue a family of textbook classics.Bird and Wadler jointly started the series with two editions of Introduction to Functional Programming (in Haskell) in 1988 and 1998, respectively.Let me begin with the outright …
Katarzyna Grygiel, Pierre Lescanne
Abstract In a paper, entitled Binary lambda calculus and combinatory logic , John Tromp presents a simple way of encoding lambda calculus terms as binary sequences. In what follows, we study the numbers of binary strings of a given size that represent lambda terms and derive resu…
Shane Hudson
Graham Hutton
Many students complete PhDs in functional programming each year. As a service to the community, the Journal of Functional Programming publishes the abstracts from PhD dissertations completed during the previous year.
Graham Hutton
Many students complete PhDs in functional programming each year. As a service to the community, the Journal of Functional Programming publishes the abstracts from PhD dissertations completed during the previous year.
Graham Hutton
Many students complete PhDs in functional programming each year, but there is currently no common location in which to promote and advertise the resulting work. The Journal of Functional Programming would like to change that!
Mauro Jaskelioff, Russell O'Connor
Abstract Representation theorems relate seemingly complex objects to concrete, more tractable ones. In this paper, we take advantage of the abstraction power of category theory and provide a datatype-generic representation theorem. More precisely, we prove a representation theore…
Hans Georg Schaathun
Abstract Pseudo-random number generation is a fundamental problem in computer programming. In the case of sequential processing the problem is very well researched, but parallel processing raises new problems whereof far too little is currently understood. Splittable pseudo-rando…
Ville Tirronen, Ville Isomöttönen
Abstract Teaching functional programming as a second programming paradigm is often difficult as students can have strong preconceptions about programming. When most of these preconceived ideas fail to be confirmed, functional programming may be seen as an unnecessarily difficult …
Ville Tirronen, Samuel Uusi-Mäkelä, Ville Isomöttönen
Abstract This article presents an overview of student difficulties in an introductory functional programming (FP) course taught in Haskell. The motivation for this study stems from our belief that many student difficulties can be alleviated by understanding the underlying causes …