Pure and Lazy Lambda Mining
This paper discusses our entry to the 2012 ICFP Programming Contest, written entirely in Haskell. Our solution uses many features of Haskell: pure immutable data structures, laziness, higher-order functions, concurrency, and exception handling. Each of th
- PDF / 303,248 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 192 Views
2
Department of Computer Science, University of Oxford, Oxford, UK {nicolas.wu, jose.pedro.magalhaes}@cs.ox.ac.uk Department of Computer Science, Utrecht University, Utrecht, The Netherlands {j.bransen, w.s.swierstra}@uu.nl
Abstract. This paper discusses our entry to the 2012 ICFP Programming Contest, written entirely in Haskell. Our solution uses many features of Haskell: pure immutable data structures, laziness, higher-order functions, concurrency, and exception handling. Each of these features plays an essential part in our overall solution, and we demonstrate how these key elements can be composed together. In this exposition, we stress the importance of how the code was structured in such a way that made safely refactoring and extending the model a relatively easy task, and how Haskell’s strong type system made it possible for our team to remain agile under changing specifications.
1
Introduction
In the classic paper Why Functional Programming Matters, Hughes [3] argues that functional programming in Miranda provides two kinds of glue that enable the modular construction of programs: lazy evaluation and higher order functions. To drive this point home, Hughes presents several small and elegant example programs that rely on precisely these features. But how useful are laziness and higher order functions in larger developments? This paper investigates this question and aims to provide further evidence supporting Hughes’s claim. We describe a solution to the 2012 ICFP programming contest.1 This programming contest allows participants to write solutions in any language, or combination of languages, in a time frame of 72 hrs. Our solution was entirely implemented in Haskell [4]. We describe our solution as it was developed in the 72 hours of the contest, plus some later refactoring for readability and bug fixing. Crucially, the solution we present uses many different Haskell features: pure immutable data structures, laziness, higher-order functions, concurrency, and exception handling.
1
Nicolas Wu and Jos´e Pedro Magalh˜ aes have been funded by EPSRC grant number EP/J010995/1. The official task description is available at http://icfpcontest2012.wordpress.com/task/. A video presenting the task and announcing the winners can be seen at https://www.youtube.com/watch?v=5TCqUU3-GT0.
R. Hinze (Ed.): IFL 2012, LNCS 8241, pp. 207–223, 2013. c Springer-Verlag Berlin Heidelberg 2013 DOI: 10.1007/978-3-642-41582-1 13,
208
N. Wu et al. Robot Earth Wall Rock Exit Lambda Higher-order rock
Fig. 1. Graphical representation of a mine
1.1
Problem Description
The ICFP programming contest has been run every year since 1998. This year, participants were invited to program a virtual mining robot to collect resources called ‘lambdas’ while avoiding falling rocks, getting trapped, or drowning. The overall score of a route was determined by the number of lambdas collected and the number of moves required to collect those lambdas. Figure 1 shows a graphical depiction of a game in progress. The goal is to compute a sequence of mo
Data Loading...
