December 2014 - Haskell-Cafe

ANN: deepseq-bounded, seqaid, leaky
by Andrew Seniuk 21 Dec '14

21 Dec '14

This trio of related packages explores strictness control in a variety of ways. deepseq-bounded provides classes and generic functions to artificially force evaluation, to extents controlled by static or dynamic configuration. seqaid puts that into practise, providing a GHC plugin to auto-instrument your package with a strictness harness, which is dynamically optimisable during runtime. This is supported directly in the GHC compilation pipeline, without requiring (or performing!) any edits to your sources. leaky is a minimal, prototypic executable that leaks space under current state-of-the-art compilation (GHC 7.8.3 -O2, at the present time). deepseq-bounded hackage: https://hackage.haskell.org/package/deepseq-bounded homepage: http://www.fremissant.net/deepseq-bounded seqaid hackage: https://hackage.haskell.org/package/seqaid homepage: http://www.fremissant.net/seqaid leaky hackage: https://hackage.haskell.org/package/leaky homepage: http://www.fremissant.net/leaky Reddit discussion for the three together: http://www.reddit.com/r/haskell/comments/2ps8f5/ann_deepseqbounded_seqaid_l… Easiest way to try them all, is to install seqaid and run the demo: cabal install seqaid seqaid demo This tests seqaid on a local copy of the leaky source package. It turned out to be routine to extend deepseq-bounded and seqaid to dynamically configurable parallelisation (paraid?). Many other wrappers could be explored, too! Maybe seqaid should be renamed to koolaid or something... It's a pretty complicated system, and just first release, so there's bound to be lots of problems. I've not set up a bug tracker, but will maintain a casual list of bugs and feature requests at http://www.fremissant.net/seqaid/trac and will set up a proper tracker if there's interest. Any isssues (or comments), I'm here, or on the reddit discussion (or email). Andrew Seniuk rasfar on #haskell

1 2

Parametric kinds
by Gautier DI FOLCO 21 Dec '14

21 Dec '14

Hello all, I'm trying to port typeclasses to kind-level, here are my data types: -- newtype Fix f a = Fix (f (Fix f a)) -- data Mu f = In (f (Mu f)) data Fix (f :: k1 -> k0) (n :: k1) = Fx data Maybe a = Nothing | Just a If I try to create type families to represent Functors, I end up with this: -- type family MapFix (f :: (* -> k) -> * -> k) a :: * where -- type family MapFix f a where type family MapFix (f :: (k0 -> k1) -> k0 -> k1) (a :: k2) :: * where MapFix f (Fix a n) = Fix (f a) (MapFix f n) -- type family MapMaybe (f :: k -> k) (a :: Maybe k) :: Maybe k where -- type family MapMaybe f a where type family MapMaybe (f :: k0 -> k1) (a :: Maybe k0) :: Maybe k1 where MapMaybe f ('Just a) = 'Just (f a) MapMaybe f 'Nothing = 'Nothing But I can't defined a single open type family for these two data types. I think I lack of parametric kinds, for example: `*k p*` could let me fit `*Maybe k*`. Currently, in the way I see kinds, on `*k0 -> k1*` allow me to parameterize kinds, but `*Maybe k*` doesn't fit. I know that this is certainly unclear, don't hesitate to ask me for clarifications. I also know that my `*Fix*` sucks, any good idea on how to do it is welcome :) Also, if you have any links to have a deeper insight of Kinds it will save me from mental illness. Thanks in advance for your help, Regards.

1 1

How to avoid keeping old data formats in your code?
by Corentin Dupont 21 Dec '14

21 Dec '14

Hi, I didn't had so much luck with this question. The question was: -> "How to avoid keeping old data formats in your code?" Indeed those old data formats are often needed for retro-compatibility with previous versions of your software. Say you have a data structure that is serialized in a file, and then you add a field in a later version. You are obliged to keep both versions of the data structure if you want to be able to read both versions of the file. Potentially, if you update very often your structure between releases, you are obliged to keep N versions of the data structure in your code. See the exemple at: http://acid-state.seize.it/safecopy On Sun, Nov 30, 2014 at 1:04 PM, Corentin Dupont <corentin.dupont(a)gmail.com> wrote: > Hi the list, > I have some question relative to data migration. > > Say you have a software in version A which save data in a file with format > FA. Later, you update your software to version B, with data format FB. > Now, if you want your version B of the software to be able to read data > saved by version A, you're obliged to include FA in version B, together > with some functions to translate from FA to FB. > > This is what I don't find elegant: you're obliged to keep old code (data > formats) in your software. > -> do you know of any way to avoid keeping old data formats (for > retro-compatiblilty) in your code? > > In practice I use acid-state with safecopy: > http://acid-state.seize.it/safecopy > In this example you can see the problem: the author is obliged to keep old > code (data structures) to maintain compatibility. Even worth, you might be > obliged to suffix your data structure with a version number: > > data MyType_V1 = MyType_V1 Intdata MyType_V2 = MyType_V2 Integer > > > Instead, I'm thinking of a process using GIT, or Cabal as a back-end. > The idea would be to have an additional program (or library) specialized > in the data migration of your main software. It would extract both version > A and B from the repo, and then would compile an application capable of > handling migrations from FA to FB. > > Does something like this exists (even outside of Haskell)? > > Cheers, > Corentin >

4 5

[ANN]Haskell Rhythm game development tutorial
by Fumiaki Kinoshita 21 Dec '14

21 Dec '14

Hello, I've published a tutorial[0] to create a rhythm game. This tutorial focuses on the design of interactive, real-time application using lens, objective, Call package. Feel free to point out infelicities or offer suggestion. Cheers [0] http://fumieval.github.io/rhythm-game-tutorial/ -- Fumiaki Kinoshita

2 2

<*> for Data.Sequence: mission accomplished
by David Feuer 20 Dec '14

20 Dec '14

All right! It's taken a long time, but I finally managed to write a nice implementation of `<*>` for `Data.Sequence`! It looks nothing like my original concept, but it accomplishes my incremental performance goals while also being a little better than the current implementation when forcing the whole result. Anyone interested can see the code in the `ap` branch of treeowl/containers on GitHub. There are still some ugly special cases for sufficiently small arguments--any ideas for changing that would be most welcome. Many thanks to Joachim Breitner for helping implement an earlier approach, to Ross Paterson for coming up with a solution to a previous formulation of the problem (thus helping me understand that I had asked the wrong question), and to Carter Schonwald for putting up with my stream of consciousness rambling. On Sun, Nov 23, 2014 at 12:07 AM, David Feuer <david.feuer(a)gmail.com> wrote: > OK, sorry for the flood of posts, but I think I've found a way to make that > work. Specifically, I think I can write a three-Seq append that takes the > total size and uses it to be as lazy as possible in the second of the three > Seqs. I'm still working out the details, but I think it will work. It does > the (possibly avoidable) rebuilding, but I *think* it's at least > asymptotically optimal. Of course, if Ross Paterson can find something more > efficient, that'd be even better. > > On Sat, Nov 22, 2014 at 10:10 PM, David Feuer <david.feuer(a)gmail.com> wrote: >> >> OK, so I've thought about this some more. I think the essential *concept* >> I want is close to this, but it won't quite work this way: >> >> fs <*> xs = equalJoin $ fmap (<$> xs) fs >> >> equalJoin :: Int -> Seq (Seq a) -> Seq a >> equalJoin n s >> | length s <= 2*n = simpleJoin s >> | otherwise = simpleJoin pref >< >> equalJoin (2*n) mid >< >> simpleJoin suff >> where (pref, s') = splitAt n s >> (mid, suff) = splitAt (length s - 2*n) s' >> >> simpleJoin :: Seq (Seq a) -> Seq a >> simpleJoin s >> | null s = empty >> | length s == 1 = index s 0 >> | otherwise = simpleJoin front >< simpleJoin back >> where >> (front,back) = splitAt (length s `quot` 2) s >> >> I think the reason this doesn't work is that >< is too strict. I believe >> the only potential way around this is to dig into the FingerTree >> representation and build the thing top-down. I still don't understand how >> (if at all) this can be done. >> >> >> On Sat, Nov 22, 2014 at 12:57 PM, David Feuer <david.feuer(a)gmail.com> >> wrote: >>> >>> The ideal goal, which has taken me forever to identify and which may well >>> be unattainable, is to get O(log(min{i,mn-i})) access to each element of the >>> result, while maintaining O(mn) time to force it entirely. Each of these is >>> possible separately, of course. To get them both, if it's possible, we need >>> to give up on the list-like approach and start splitting Seqs instead of >>> lists. As we descend, we want to pass a single thunk to each element of each >>> Digit to give it just enough to do its thing. Representing the splits >>> efficiently and/or memoizing them could be a bit of a challenge. >>> >>> On Fri, Nov 21, 2014 at 02:00:16PM -0500, David Feuer wrote: >>> > To be precise, I *think* using the fromList approach for <*> makes us >>> > create O >>> > (n) thunks in order to extract the last element of the result. If we >>> > build the >>> > result inward, I *think* we can avoid this, getting the last element of >>> > the >>> > result in O(1) time and space. But my understanding of this data >>> > structure >>> > remains primitive. >>> >>> This modification of the previous should do that. >>> >>> mult :: Seq (a -> b) -> Seq a -> Seq b >>> mult sfs sxs = fromTwoLists (length sfs * length sxs) ys rev_ys >>> where >>> fs = toList sfs >>> rev_fs = toRevList sfs >>> xs = toList sxs >>> rev_xs = toRevList sxs >>> ys = [f x | f <- fs, x <- xs] >>> rev_ys = [f x | f <- rev_fs, x <- rev_xs] >>> >>> -- toRevList xs = toList (reverse xs) >>> toRevList :: Seq a -> [a] >>> toRevList = foldl (flip (:)) [] >>> >>> -- Build a tree lazy in the middle, from a list and its reverse. >>> -- >>> -- fromTwoLists (length xs) xs (reverse xs) = fromList xs >>> -- >>> -- Getting the kth element from either end involves forcing the lists >>> -- to length k. >>> fromTwoLists :: Int -> [a] -> [a] -> Seq a >>> fromTwoLists len_xs xs rev_xs = >>> Seq $ mkTree2 len_xs 1 (map Elem xs) (map Elem rev_xs) >>> >>> -- Construct a fingertree from the first n elements of xs. >>> -- The arguments must satisfy n <= length xs && rev_xs = reverse xs. >>> -- Each element of xs has the same size, provided as an argument. >>> mkTree2 :: Int -> Int -> [a] -> [a] -> FingerTree a >>> mkTree2 n size xs rev_xs >>> | n == 0 = Empty >>> | n == 1 = let [x1] = xs in Single x1 >>> | n < 6 = let >>> nl = n `div` 2 >>> l = Data.List.take nl xs >>> r = Data.List.take (n - nl) rev_xs >>> in Deep totalSize (mkDigit l) Empty (mkRevDigit r) >>> | otherwise = let >>> size' = 3*size >>> n' = (n-4) `div` 3 >>> digits = n - n'*3 >>> nl = digits `div` 2 >>> (l, xs') = Data.List.splitAt nl xs >>> (r, rev_xs') = Data.List.splitAt (digits - nl) rev_xs >>> nodes = mkNodes size' xs' >>> rev_nodes = mkRevNodes size' rev_xs' >>> in Deep totalSize (mkDigit l) (mkTree2 n' size' nodes rev_nodes) >>> (mkRevDigit r) >>> where >>> totalSize = n*size >>> >>> mkDigit :: [a] -> Digit a >>> mkDigit [x1] = One x1 >>> mkDigit [x1, x2] = Two x1 x2 >>> mkDigit [x1, x2, x3] = Three x1 x2 x3 >>> mkDigit [x1, x2, x3, x4] = Four x1 x2 x3 x4 >>> >>> -- length xs <= 4 => mkRevDigit xs = mkDigit (reverse xs) >>> mkRevDigit :: [a] -> Digit a >>> mkRevDigit [x1] = One x1 >>> mkRevDigit [x2, x1] = Two x1 x2 >>> mkRevDigit [x3, x2, x1] = Three x1 x2 x3 >>> mkRevDigit [x4, x3, x2, x1] = Four x1 x2 x3 x4 >>> >>> mkNodes :: Int -> [a] -> [Node a] >>> mkNodes size (x1:x2:x3:xs) = Node3 size x1 x2 x3:mkNodes size xs >>> >>> -- length xs `mod` 3 == 0 => >>> -- mkRevNodes size xs = reverse (mkNodes size (reverse xs)) >>> mkRevNodes :: Int -> [a] -> [Node a] >>> mkRevNodes size (x3:x2:x1:xs) = Node3 size x1 x2 x3:mkRevNodes size xs >>> _______________________________________________ >>> Haskell-Cafe mailing list >>> Haskell-Cafe(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >> >

2 3

LambdaConf 2015 - CFP
by John A. De Goes 20 Dec '14

20 Dec '14

Hi all, LambdaConf 2015 has officially opened its Call for Proposals. LambdaConf 2015 is being held in the beautiful foothills of the Rocky Mountains, in Boulder, Colorado (home to many companies using FP). The conference is devoted to helping people become better programmers through functional and declarative programming. We're looking for lightning talks, workshops, and presentations on the following themes: FP 101. Introductory material for the FP curious or those just getting their feet wet. Languages. New languages (functional / logic), functional ways to use existing languages, language extensions, etc. Theory. Type theory, category theory, abstract algebra, ongoing or new research, and anything useful or interesting to functional programmers or academics working in the field. Libraries. Cool libraries that demonstrate the power of functional programming in helping programmers get stuff done. Case Studies. Case studies showing how using a functional language or library proved to be game-changing in solving real world problems. We currently have talks or workshops lined up for Haskell, Purescript, Scala, and Rust. If you'd like to submit a proposal, just send a private email to me or visit the official website for more information. We are not yet open for registrations, but we are actively looking for a couple more volunteers, as well as sponsors. If you know someone who might be interested, please spread the word! Regards, John

1 0

Random pattern generation with list comprehensions
by Mike Jones 20 Dec '14

20 Dec '14

I am looking for a way to generate random patterns for hardware validation. The goal is to separate patten generation from execution in hardware, and from pure code used to compute expected behavior from a model, detection of bad behavior, in the form of predicates, etc. The purpose of random patterns is to explore the behavior space in less time, as well as improve time to discovery by preventing long runs that focus in narrow areas for long periods. Patterns are to be infinite lists with the ability to specify run length for any run, which becomes a quality dial of sorts. I initially started with finite sequences expressed as list comprehensions, that generate tuples of ints, floats, structured data, and lists of attributes (bit combinations of hardware registers). I believe the list comprehension evaluates each generator (a | a <- ...) in a strict order, such that an infinite list will cause infinite evaluation of a single generator, such that other generators are not evaluated. Even if each generator is constrained (take n), results will not not be completely random. What I need is for each generator to supply one value each, and combine them into a tuple. I could probable express this in a monadic loop construct, as long as each generator is random and holds state, like the article I saw using the State Monad to generate random numbers. Or perhaps a State monad that holds multiple generators. Is there a better way to express the solution or a helpful module others use for this? Mike Sent from my iPad

5 5

HPC and Template Haskell (GHC 7.8.3, Yesod)
by David Turner 19 Dec '14

19 Dec '14

Hi, I'm having trouble making a HPC build of a Yesod application. It fails with: /usr/bin/ld: dist/build/StreamReading/Config.dyn_o: relocation R_X86_64_PC32 against undefined symbol `_hpc_tickboxes_tracszmenterprisezm0zi0zi0_Settings_hpc' can not be used when making a shared object; recompile with -fPIC I've narrowed it down to a call to ghc and posted the output in all its gory detail at http://lpaste.net/116872 if that's any help. Of note is that dist/build/Settings.dyn_o is unexpectedly missing from the list of parameters to the last call to gcc, and the missing symbol is defined in the same. There are, in fact, quite a number of missing .dyn_o files in that list. Slightly weirdly, when I run the same command line again, it seems to work. At least, there are no errors reported and the exit code is 0. Any ideas? Cheers, David

2 2

Hackage 2 archive.tar equivalent
by Alexander Solla 19 Dec '14

19 Dec '14

On the old hackage site (running Hackage 1.*), we used to be able to download a file called archive.tar, which contained the latest version of all of the Haskell packages. Is there any way to do this with Hackage 2? I understand that my case is definitely a corner case -- I don't have a regular net connection, so I'd really like to be able to download a snapshot of Hackage at regular, convenient intervals, and serve them up at home.

2 1

[TFP 2015] 1st call for papers
by Peter Achten 19 Dec '14

19 Dec '14

----------------------------- C A L L F O R P A P E R S ----------------------------- ======== TFP 2015 =========== 16th Symposium on Trends in Functional Programming June 3-5, 2015 Inria Sophia Antipolis, France http://tfp2015.inria.fr/ The symposium on Trends in Functional Programming (TFP) is an international forum for researchers with interests in all aspects of functional programming, taking a broad view of current and future trends in the area. It aspires to be a lively environment for presenting the latest research results, and other contributions (see below). Authors of draft papers will be invited to submit revised papers based on the feedback receive at the symposium. A post-symposium refereeing process will then select a subset of these articles for formal publication. The selected revised papers are expected to be published as a Springer Lecture Notes in Computer Science (LNCS) volume. TFP 2015 will be the main event of a pair of functional programming events. TFP 2015 will be accompanied by the International Workshop on Trends in Functional Programming in Education (TFPIE), which will take place on June 2nd. The TFP symposium is the heir of the successful series of Scottish Functional Programming Workshops. Previous TFP symposia were held in * Edinburgh (Scotland) in 2003; * Munich (Germany) in 2004; * Tallinn (Estonia) in 2005; * Nottingham (UK) in 2006; * New York (USA) in 2007; * Nijmegen (The Netherlands) in 2008; * Komarno (Slovakia) in 2009; * Oklahoma (USA) in 2010; * Madrid (Spain) in 2011; * St. Andrews (UK) in 2012; * Provo (Utah, USA) in 2013; * and in Soesterberg (The Netherlands) in 2014. For further general information about TFP please see the TFP homepage. (http://www.tifp.org/) == INVITED SPEAKERS == TFP is pleased to announce talks by the following two invited speakers: * Laurence Rideau is a researcher at INRIA and is interested in the semantics of programming languages , the formal methods, and the verification tools for programs and mathematical proofs. She participated in the beginnings of the Compcert project (certified compiler), and is part of the Component Mathematical team in the MSR-INRIA joint laboratory, who performed the formalization of the Feit-Thompson theorem successfully. Thirty years ago, computers barged in mathematics with the famous proof of the Four Color Theorem. Initially limited to simple calculation, their role is now expanding to the reasoning whose complexity is beyond the capabilities of most humans, as the proof of the classification of finite simple groups. We present our large collaborative adventure around the formalization of the Feit-Thompson theorem (http://en.wikipedia.org/wiki/Feit%E2%80%93Thompson_theorem) that is a first step to the classification of finite groups and that uses a palette of methods and techniques that range from formal logic to software (and mathematics) engineering. * Sam Aaron (?) == SCOPE == The symposium recognizes that new trends may arise through various routes. As part of the Symposium's focus on trends we therefore identify the following five article categories. High-quality articles are solicited in any of these categories: Research Articles: leading-edge, previously unpublished research work Position Articles: on what new trends should or should not be Project Articles: descriptions of recently started new projects Evaluation Articles: what lessons can be drawn from a finished project Overview Articles: summarizing work with respect to a trendy subject Articles must be original and not simultaneously submitted for publication to any other forum. They may consider any aspect of functional programming: theoretical, implementation-oriented, or experience-oriented. Applications of functional programming techniques to other languages are also within the scope of the symposium. Topics suitable for the symposium include: Functional programming and multicore/manycore computing Functional programming in the cloud High performance functional computing Extra-functional (behavioural) properties of functional programs Dependently typed functional programming Validation and verification of functional programs Debugging and profiling for functional languages Functional programming in different application areas: security, mobility, telecommunications applications, embedded systems, global computing, grids, etc. Interoperability with imperative programming languages Novel memory management techniques Program analysis and transformation techniques Empirical performance studies Abstract/virtual machines and compilers for functional languages (Embedded) domain specific languages New implementation strategies Any new emerging trend in the functional programming area If you are in doubt on whether your article is within the scope of TFP, please contact the TFP 2015 program chair, Manuel Serrano. == BEST PAPER AWARDS == To reward excellent contributions, TFP awards a prize for the best paper accepted for the formal proceedings. TFP traditionally pays special attention to research students, acknowledging that students are almost by definition part of new subject trends. A student paper is one for which the authors state that the paper is mainly the work of students, the students are listed as first authors, and a student would present the paper. A prize for the best student paper is awarded each year. In both cases, it is the PC of TFP that awards the prize. In case the best paper happens to be a student paper, that paper will then receive both prizes. == SPONSORS == TFP is financially supported by ?????????????????? == PAPER SUBMISSIONS == Acceptance of articles for presentation at the symposium is based on a lightweight peer review process of extended abstracts (4 to 10 pages in length) or full papers (20 pages). The submission must clearly indicate which category it belongs to: research, position, project, evaluation, or overview paper. It should also indicate which authors are research students, and whether the main author(s) are students. A draft paper for which ALL authors are students will receive additional feedback by one of the PC members shortly after the symposium has taken place. We use EasyChair for the refereeing process. Papers must be submitted at: https://easychair.org/conferences/?conf=tfp2015 Papers must be written in English, and written using the LNCS style. For more information about formatting please consult the Springer LNCS web site: http://www.springer.com/computer/lncs?SGWID=0-164-6-793341-0 == IMPORTANT DATES == Submission of draft papers: March 17, 2015 Notification: March 24, 2015 Registration: April 7, 2015 TFP Symposium: June 3-5, 2015 Student papers feedback: June 9, 2015 Submission for formal review: July 1, 2015 Notification of acceptance: September 8, 2015 Camera ready paper: October 8, 2015 == PROGRAM COMMITTEE == Janis Voigtländer University of Bonn, DE Scott Owens University of Kent, UK Neil Sculthorpe Swansea University, UK Colin Runciman University of York, UK Manuel Serrano Inria (PC chair), FR Rinus Plasmeijer University of Nijmegen, NL Tomas Petricek University of Cambridge, UK Marco T. Morazan Seton Hall University, USA Wolfgang De Meuter Vrije Universiteit Brussel, BE Michel Mauny Ensta ParisTech, FR Sam Lindley The University of Edinburgh, UK Daan Leijen Microsoft, USA Jurriaan Hage Utrecht University, NL Andy Gill University of Kansas, USA Thomas Gazagnaire University of Cambrige, UK Lars-Ake Fredlund Universidad Politécnica de Madrid, ES Jean-Christophe Filliatre Université Paris Sud Orsay, FR Marc Feeley Université de Montréal, CA Olaf Chitil University of Kent, UK Edwin Brady University of St Andrews, UK

1 0