News aggregator

ICFP 2014 Student Research Competition: Call forSubmissions

haskell-cafe - Fri, 05/16/2014 - 9:29pm
====================================================================== CALL FOR SUBMISSION SRC< at >ICFP 2014 Gothenburg, Sweden 1-3 September 2014 http://www.icfpconference.org/icfp2014/src.html Co-located with the International Conference on Functional Programming (ICFP 2014) ====================================================================== Student Research Competition ------------------------ This year ICFP will host a Student Research Competition where undergraduate and postgraduate students can present posters. The SRC at the ICFP 2014 consists of three rounds: Extended abstract round: All students are encouraged to submit an extended abstract outlining their research (800 words). Poster session at ICFP 2014: Based on the abstracts, a panel of judges will select the most promising entrants to participate in the poster session which will take place at ICF
Categories: Offsite Discussion

ICFP 2014 Student Research Competition: Call forSubmissions

General haskell list - Fri, 05/16/2014 - 9:29pm
====================================================================== CALL FOR SUBMISSION SRC< at >ICFP 2014 Gothenburg, Sweden 1-3 September 2014 http://www.icfpconference.org/icfp2014/src.html Co-located with the International Conference on Functional Programming (ICFP 2014) ====================================================================== Student Research Competition ------------------------ This year ICFP will host a Student Research Competition where undergraduate and postgraduate students can present posters. The SRC at the ICFP 2014 consists of three rounds: Extended abstract round: All students are encouraged to submit an extended abstract outlining their research (800 words). Poster session at ICFP 2014: Based on the abstracts, a panel of judges will select the most promising entrants to participate in the poster session which will take place at ICF
Categories: Incoming News

what did it take for you to get comfortable with Haskell ?

Haskell on Reddit - Fri, 05/16/2014 - 8:43pm

is it books you read, courses, meetings, projects you worked on...etc

submitted by pyThat
[link] [28 comments]
Categories: Incoming News

How do I learn Fay?

Haskell on Reddit - Fri, 05/16/2014 - 6:20pm

I've recently become interested in Haskell, and I'm working on my first project, a tic-tac-toe game. I have gotten the game to work on the command line, but I would also like to build a better interface with Fay/Javascript.

The problem is that I haven't found any good tutorials or explanations of Fay. Does anyone know any good resources for Fay, or should I just study the examples that are provided in the package?

submitted by Judde10
[link] [4 comments]
Categories: Incoming News

Parent Modules: Common Functions or Re-Exportation?

haskell-cafe - Fri, 05/16/2014 - 6:13pm
So as a relatively long term user of haskell at this point, one issue which I've never found a simple solution to is the one stated in the thread. That is, given modules Foo, Foo.Bar, and Foo.Baz, should Foo reexport Bar and Baz, or should Foo provide common functions for Bar and Baz? In the first case, the common functions would have to be provided by some third module Foo.Util, which for some reason I find unsatisfying, as it means all my my modules have these Util after Util after Util module floating aroudn. My natural tendency is follow the second case, but then of course when it comes to actually using the code that I've written, I no longer have such a nicely exposed interface outside of the particular library. One simply can't eat ones cake and have it too. Maybe this problem is just silly, but perhaps others have always been left feeling ambivalent across similar lines, and have somehow found a pleasant solution for when this particular crossroads is reached? Cheers, - Sacha Sokol
Categories: Offsite Discussion

Home · faylang/fay Wiki

del.icio.us/haskell - Fri, 05/16/2014 - 4:13pm
Categories: Offsite Blogs

Caching intermediate powers in GHC.Float

glasgow-user - Fri, 05/16/2014 - 4:11pm
Does the following make sense: https://ghc.haskell.org/trac/ghc/ticket/9120 Bas
Categories: Offsite Discussion

mightybyte: Implicit Blacklisting for Cabal

Planet Haskell - Fri, 05/16/2014 - 2:11pm

I've been thinking about all the Haskell PVP discussion that's been going on lately. It should be no secret by now that I am a PVP proponent. I'm not here to debate the PVP in this post, so for this discussion let's assume that the PVP is a good thing and should be adopted by all packages published on Hackage. More specifically, let's assume this to mean that every package should specify upper bounds on all dependencies, and that most of the time these bounds will be of the form "< a.b".

Recently there has been discussion about problems encountered when packages that have not been using upper bounds change and start using them. The recent issue with the HTTP package is a good example of this. Roughly speaking the problem is that if foo-1.2 does not provide upper bounds on it's dependency bar, the constraint solver is perpetually "poisoned" because foo-1.2 will always be a candidate even long after bar has become incompatible with foo-1.2. If later foo-3.9 specifies a bound of bar < 0.5, then when bar-0.5 comes out the solver will try to build with foo-1.2 even though it is hopelessly old. This will result in build errors since bar has long since changed its API.

This is a difficult problem. There are several immediately obvious approaches to solving the problem.

  1. Remove the offending old versions (the ones missing upper bounds) from Hackage.
  2. Leave them on Hackage, but mark them as deprecated/blacklisted so they will not be chosen by the solver.
  3. Go back and retroactively add upper bounds to the offending versions.
  4. Start a new empty Hackage server that requires packages to specify upper bounds on all dependencies.
  5. Start a new Hackage mirror that infers upper bounds based on package upload dates.

All of these approaches have problems. The first three are problematic because they mess with build reproducibility. The fourth approach fragments the community and in the very best case would take a lot of time and effort before gaining adoption. The fifth approach has problems because correct upper bounds cannot always be inferred by upload dates.

I would like to propose a solution I call implicit blacklisting. The basic idea is that for each set of versions with the prefix a.b.c Cabal will only consider a single one: the last one. This effectively means that all the lower versions with the prefix a.b.c will be implicitly blacklisted. This approach should also allow maintainers to modify this behavior by specifying more granular version bounds.

In our previous example, suppose there were a number of 0.4 versions of the bar package, with 0.4.3.3 being the last one. In this case, if foo specified a bound of bar < 0.5, the solver would only consider 0.4.3.3. 0.4.3.2 and 0.4.3.1 would not be considered. This would allow us to completely hide a lack of version bounds by making a new patch release that only bumps the d number. If that release had problems, we could address them with more patch releases.

Now imagine that for some crazy reason foo worked with 0.4.3.2, but 0.4.3.3 broke it somehow. Note that if bar is following the PVP, that should not be the case. But there are some well-known cases where the PVP can miss things and there is always the possibility of human error. In this case, foo should specify a bound of bar < 0.4.3.3. In this case, the solver should respect that bound and only consider 0.4.3.2. But 0.4.3.1 would still be ignored as before.

Implicit blacklisting has the advantage that we don't need any special support for explicitly marking versions as deprecated/blacklisted. Another advantage is that it does not cause any problems for people who had locked their code down to using specific versions. If foo specified an exact version of bar == 0.4.3.0, then that will continue to be chosen. Implicit blacklisting also allows us to leave everything in hackage untouched and fix issues incrementally as they arise with the minimum amount of work. In the above issue with HTTP-4000.0.7, we could trivially address it by downloading that version, adding version bounds, and uploading it as HTTP-4000.0.7.1.

All in all, I think this implicit blacklisting idea has a number of desirable properties and very few downsides. It fixes the problem using nothing but our existing infrastructure: version numbers. It doesn’t require us to add new concepts like blacklisted/deprecated flags, out-of-band “revision” markers to denote packages modified after the fact, etc. But since this is a complicated problem I may very well have missed something, so I'd like to hear what the community thinks about this idea.

Categories: Offsite Blogs

Shake as a dependency library

Haskell on Reddit - Fri, 05/16/2014 - 12:42pm
Categories: Incoming News

Looking for companies using Haskell to visit in the Bay Area.

Haskell on Reddit - Fri, 05/16/2014 - 5:14am

Our team of Haskellers (aka the Lambda Team) from Prezi's Budapest office is planning to spend a month in SF this summer. We're looking to connect and share experiences with other companies using Haskell.

submitted by mate-kovacs
[link] [13 comments]
Categories: Incoming News

Are Ana-/Catamorphisms just slower? [SO question]

Haskell on Reddit - Fri, 05/16/2014 - 3:33am

Are Ana-/Catamorphisms just slower?

I posted a question to SO yesterday and while it was well received (upvote wise) I failed to get any answer.

So as to broaden the audience I repost it here.

submitted by goliatskipson
[link] [11 comments]
Categories: Incoming News

www.youtube.com

del.icio.us/haskell - Fri, 05/16/2014 - 2:46am
Categories: Offsite Blogs

MonadIO instance where liftIO can't be used outside of the module?

Haskell on Reddit - Fri, 05/16/2014 - 2:45am

I'm wanting to implement a MonadIO instance that uses liftIO internally in its own functions, but such that liftIO cannot be used other modules that import this monad, effectively restricting it to a known subset of IO functions. Is this possible?

submitted by jmere
[link] [5 comments]
Categories: Incoming News

language-puppet: 7 Startups - part 3 - An interpreter for the rules

Planet Haskell - Thu, 05/15/2014 - 11:31pm

In the previous episode I implemented the game rules, but did not test them. I also had some reservations about some code I wrote, but predicted it would be mostly right, even without tests. Today’s episode is about pretty printing and operational !

Minor modifications since last time
  • I refactored the getCardFunding and getCardVictory functions so that they are now pure. I toyed with the idea of having a monad morphism (I learned today it was called like that to integrate Reader GameState actions in the MonadState GameState functions, but this was not warranted as the functions are so simple.
  • I refactored neighborhood relationship so that it encodes more invariants. A player now must have a left and right neighbor. They might be invalid though.
  • I refactored the type of the interfaces between the game rules and the players, so that you can’t pass empty lists where they are forbidden. I was later told this type already existed in semigroups.
Why pretty printing ?

I hinted heavily last time that there would be a dedicated pretty printer. An example of such an implementation is in the ansi-wl-pprint package. It introduces functions and combinators that let you easily create a Doc value that will look neat on your screen.

Unfortunately, in order to properly support all text-based backends (IRC, XMPP, email, console) it doesn’t seem to be possible to reuse an existing printer. For example, the color set between all these backends is quite distinct, and some are even capable of printing pictures. I tried to engineer one that would be at the same time flexible, easy to use and good-looking an all backends. Time will tell if this was a success.

I will not give a dissertation on the subject, and have copied the interface from other pretty printing libraries. I will just give some implementation details here.

Basic pretty printing types

Speaking of stealing from other pretty printers, I really should have looked at their code too ! Here are my basic types:

<figure class="code"> 1 2 3 4 5 6 7 newtype PrettyDoc = PrettyDoc { getDoc :: Seq PrettyElement } deriving (Eq, Monoid) data PrettyElement = RawText T.Text | NewLine | Space | ... </figure>

So you basically have all “elements” in PrettyElement, and they can be appended in a monoidal fashion in a PrettyDoc, which is just a newtype for Seq PrettyElement. This is a very inelegant decision, and I will be sure to refactor it for the next episode ! Looking at another implementation, it is clear that a single type was required, and that the Monoidal structure could be achieved by adding Empty and Cat constructors. There is a reason I wrote my type like this though, and it is related to how I intended to solve the problem of backends with poor or no support for multiline messages, but this will featured in another episode !

Specific design choices

I decided to directly encode the game entities as part of the pretty printing types. That should be obvious from the list of elements. A VictoryPoint, a Neighbor or even a CardType are directly representable, so that the backends can optimize their rendering.

Other than that, the code is pretty boring.

A pretty-pretty printer ?

My first backend will be the console, as it will not have any networking or concurrency problems to solve. I used the aforementioned ansi-wl-pprint package, and wrote a pretty instance for PrettyElement and PrettyDoc. This leads to strange code such as print (PP.pretty (pe something)).

Implementing the GameMonad

During the last episode, I wrote all the rules in an abstract monad that is an instance of GameMonad, meaning it featured a few functions for interacting with the players. I took a typeclass approach so that I could start writing the rules without worrying about the actual implementation of this abstract monad.

Now that the rules are written, it is time to give them a try. In order to do so, I ditched the typeclass, and expressed it in terms of ProgramT, from the operational package. It only takes a few steps to refactor :

The instructions GADT

You must start by writing all the operations that must be supported as a GADT.

We previously had :

<figure class="code"> 1 2 3 4 5 6 7 8 9 10 11 type NonInteractive m = (MonadState GameState m, Monad m, MonadError Message m, Functor m, Applicative m) class NonInteractive m => GameMonad m where playerDecision :: Age -> Turn -> PlayerId -> [Card] -> GameState -> m (PlayerAction, Exchange) askCard :: Age -> PlayerId -> [Card] -> GameState -> Message -> m Card tellPlayer :: PlayerId -> Message -> m () generalMessage :: Message -> m () </figure>

And now have :

<figure class="code"> 1 2 3 4 5 6 7 8 data GameInstr a where PlayerDecision :: Age -> Turn -> PlayerId -> NonEmpty Card -> GameInstr (PlayerAction, Exchange) AskCard :: Age -> PlayerId -> NonEmpty Card -> Message -> GameInstr Card TellPlayer :: PlayerId -> Message -> GameInstr () GeneralMessage :: Message -> GameInstr () ActionsRecap :: M.Map PlayerId (PlayerAction, Exchange) -> GameInstr () ThrowError :: Message -> GameInstr a CatchError :: GameMonad a -> (Message -> GameMonad a) -> GameInstr a </figure>

So … there have been some choices going on here. First of all, we need to support all the features we previously had, namely MonadState, MonadError and four game-specific functions. You can spot these four functions quite easily (along with a new one, which will be covered in a minute). We get MonadState and MonadError in the following way :

<figure class="code"> 1 2 3 4 5 type GameMonad = ProgramT GameInstr (State GameState) instance MonadError PrettyDoc (ProgramT GameInstr (State GameState)) where throwError = singleton . ThrowError catchError a handler = singleton (CatchError a handler) </figure>

I decided to use the monad transformer ProgramT over a base State GameState monad, but encode the error part with the provided instructions. It would have been easier to encode the state part that way, except I don’t know how to write an instance for ProgramT (see this post comment).

The interaction functions no longer have a GameState in their types, because the interpreter will have access to the state when decoding this instruction, so it is not necessary to pass it here too.

Mechanically refactor all mentions of GameMonad

Now all you have to do is to replace all type signatures that looked like :

<figure class="code"> 1 GameMonad m => a -> b -> m c </figure>

Into :

<figure class="code"> 1 a -> b -> GameMonad c </figure> Write an interpreter

I decided to write a generic interpreter, that takes a group of functions in some monad m, a base GameState, and gives you a function that computes any GameMonad a expression in the m monad. The implementation is pretty obvious, and not very interesting, but it should be easy to write backends now.

Perhaps of interest is the fact that the game state is explicitly passed as a parameter all over the place, so it can be passed to the backends at the interpreter level.

A pure backend

The easiest backend to write is a pure one, with no real player interaction. I could have used Identity as the base monad, but instead opted for State StdGen. That way, I can easily have the “players” play random cards, which will help with testing.

The implementation is also nothing special, but made me write a lot of code to support it. In particular, the allowableActions function is pretty tricky, and is not entirely satisfying. Given a game state, a player name and a list of cards in his hands, it gives a list of all the non obviously stupid legal actions that are available. It does so in the most direct way, enumerating all possible combinations of resources, neighbor resources, exchanges, etc. that would work. Then it removes all duplicates, and the actions that are obviously too expensive.

Fortunately, all this code will also be used by the other backends.

So … are there bugs yet ?

I wrote a simple test that checks for errors. Theoretically, the pure backend should always result in games that end well (we should get a Right ... instead of a Left rr. So I wrote a simple property-based test that gets an arbitrary seed and number of players (between 3 and 7), runs a pure game and checks its result.

And there were runtime errors !

  • The Monoid instance for AddMap had an infinite loop.
  • The allowableActions function sometimes returned no valid actions. I forgot to always add the possibility to drop a card …

To prevent the second case from happening again, I wrote the “prepend drop actions” before the big case statement, and modified the type of the askCardSafe function so that it can’t accept an empty list. This means that if I introduce another bug in allowableActions, I should get a Left ... instead of a runtime exception.

There also was a “rule” bug, due to the fact that I had not understood a rule correctly. Basically, I use a fictional 7Th round to emulate the efficiency capability, but there should be no “hand rotation” before that turn. I fixed it wrong once, and then properly. However, I did not discover nor fix this bug because of tests.

The console backend

Before writing the console backend I needed a bit of code for pretty printing stuff. Once this was done, the backend was quickly written.

The opponents still play randomly, which explains the kind of results depicted below, but it is a genuine pleasure to finally play !

I also realized when using the console backends that the messaging functions, while generic, would probably not work well on all backends. I decided to include more specialized functions, such as ActionsRecap, which can be passed a map of all the actions the players undertook in a turn. The current version also lacks a way of getting the results of the poacher wars between the ages, but that should be trivial to add.

Next time

Next time should get more interesting, as I will try to write an interesting backend. It will be a bit harder to design because I want players using distinct backends to be able to participate in the same game.

Categories: Offsite Blogs

Object oriented haskell.

haskell-cafe - Thu, 05/15/2014 - 6:38pm
Hi Haskell, I've been wondering if (.) is so cool in other languages why can't we make it even cooler in haskell. And went on to implement such a (.) based on multiparameter type classes and type families. type family Output object action class Action object action where (.) :: object -> action -> Output object action I'm not sure if this has been done before like this but i didn't find anything. I used Map as an example, and here is what I ended up with: fromList [('f',Just 1),('o',Nothing)] Just 1 2 I also have a pretty cool (almost) solution to the name collision problem. Visit the project homepage for a more thorough explanation. https://github.com/yokto/object And to those who gonna hate on me because they like the (.) as function composition I have only this to say. type instance Output (b -> c) (a -> b') = (a -> c) instance (b ~ b') => Action (b -> c) (a -> b') where f . g = f Prelude.. g Have fun, Silvio
Categories: Offsite Discussion

Danny Gratzer: Grokking recursion-scheme: Part 1

Planet Haskell - Thu, 05/15/2014 - 6:00pm
Posted on May 16, 2014

This post is a little different than the rest of my blog, I’m not nearly as competent with recursion-schemes as I want to be and I don’t understand them fully (yet). This isn’t entirely complete, but I hope it will provide a useful intuition for how to work with some of the lower ends of recursion-schemes and some idea of how to get into the higher end. I’ll be reading this again in two weeks once I’ve forgotten all of this (again). You’ve been warned…

Why Bother?

First, let’s talk about why anyone would care about using a library like recursion-schemes.

Remember back in the good old days when all a programmer was goto and guts? And everyone hated it? We’re at a not dissimilar place in Haskell. Well, it’s not nearly so bad nowadays, however, our principle form of control flow is recursion and really we mostly use recursion in a raw, unprincipled way.

However, we’re starting to move away from it. Do these look familiar?

foldr :: (a -> b -> b) -> b -> [a] -> b foldr f nil (x : xs) = x `f` foldr f nil xs foldr f nil [] = nil

foldr is all about abstracting away raw recursion! foldr is great in this way since it covers a surprisingly large cover of cases

map :: (a -> b) -> [a] -> [b] map f = foldr ((:) . f) filter :: (a -> Bool) -> [a] -> [a] filter p = foldr (\x rest -> if p x then x : rest else rest)

Turns out you can implement quite a lot of Data.List with foldr and poor judgment.

However, this isn’t good enough. For example, I do a lot of work with compilers and therefore spend a lot of time doing transformations on trees. I want something like foldr to deal with this.

recursion-schemes is one such option. It’s a way of generalizing these uniform transformations on structures and it’s expanded to cover a lot transformations.

On to recursion-schemes

Now that we know that recursion-schemes is solving a useful problem, let’s get into actually using it. First, we can install it off of hackage

cabal install recursion-schemes

And import everything with

{-# LANGUAGE TypeFamilies, DeriveFunctor #-} import Data.Functor.Foldable

Let’s get started by seeing how recursion-schemes covers foldr

First, we define our own custom list

data MyList a = MyCons a (MyList a) | MyNil

Next, we define another type of list, with the recursion factored out

data BList a b = BCons a b | BNil deriving Functor

Here b is the recursive bit of BList factored out into an explicit parameter. So

MyList a ~ BList a (BList a (BList a ....))

The fancy term for this would be to say that List a is the “fixed point” for BList a.

Now we can actually use recursion-schemes

type instance Base (List a) = BList a instance Foldable (List a) where project (MyCons a b) = BCons a b project MyNil = BNil

And we’re done. So to understand what’s going on we need to talk about another data type and a little math.

newtype Fix f a = Fix {unFix :: f (Fix f a)}

Remember before how I mentioned how MyList is the fixed point of BList? Well Fix let’s us exploit this fact. In particular

out :: Fix (BList a) -> MyList a out (Fix (BCons a rest)) = MyCons a (out rest) into :: MyList a -> Fix (BList a) into (MyCons a rest) = Fix (BCons a $ into rest)

So we could write either BList or MyList for all our data types, but the BList version is really a pain to write since everything is wrapped in Fix. Unfortunately though, it’s much easier to write generic code for stuff of the form Fix (f a).

To solve this recursion-schemes has the type class Base where we map the recursive data type to its non-recursive friend. Then, in project we define how to.. well.. project the recursive into a partially unfolded equivalent.

With just those two steps, we get a large chunk of recursion-schemes operations for our data type!

Just What Did We Get?

Now this was the part I really had trouble with in recursion-schemes the names of the functions for Foldable are… opaque if you’re not familiar with the terminology.

The most basic one is cata, which is the “catamorphism” across our data type. I’m not going to trouble you with why we call it a catamorphism, but just remember that it’s the souped-up version of foldr.

foldr :: (a -> b -> b) -> b -> [a] -> b foldr :: ((a, b) -> b) -> b -> [a] -> b cata :: (Fix BList a -> b) -> List a -> b cata :: (Base (List a) a -> b) -> List a -> b cata :: (Base t b -> b) -> t -> b

And we can use it the same way!

map :: (a -> b) -> List a -> List b map f = cata mapper where mapper (BCons a b) = f a `MyCons` b mapper BNil = MyNil myfilter :: (a -> Bool) -> List a -> List a myfilter p = cata filterer where filterer (BCons a b) = if p a then a `MyCons` b else b filterer BNil = MyNil

Now we can all tell people that we’ve written map using a catamorphism.

Careful readers will notice one big difference between foldr and cata: cata doesn’t take a seed! Indeed with foldr we replace all the constructors of our list with the function f, so

1 : 2 : 3 : 4 : [] 1 `f` 2 `f` 3 `f` 4 `f` seed

This doesn’t generalize well though, what if we have a type with a constructor of 3 arguments? Or 5? To avoid this problem, recursion-schemes takes a clever approach.

Remember that BList factors out recursion? cata works by collapsing a sublist recursively and sticking the slot back into the slot of the original list. So we actually have something like

BCons 1 (BCons 2 (BCons 3 (BCons 4 BNil))) BCons 1 (f (BCons 2 (f (BCons 3 (f (BCons 4 (f Nil)))))))

Now f has to handle all possible cases of our constructor, so it handles both the seed value and the collapsing case! And this generalizing beautifully by just delegating all the constructor specific work to f this is how it’s possible to derive cata practically for free.

Now, since recursion-schemes already has an instance for [a], I’ll dispense with MyList since it’s a bit clunky.

Our foldable instance gives us quite a bit more than just foldr however! We also get this function para, short for “paramorphisms”. A paramorphism is like a fold, but also gives a “snapshot” of the structure at the point we’re folding. So if we wanted to sum each tail of a list, we could do something like

sumTails :: Num a => [a] -> [a] sumTails = para summer where summer (Cons a (list, rest)) = a + sum list : rest summer Nil = []

This could be useful for example, if you’re doing any context dependent operations on a structure. Later, I’ll try to include some more practical examples of a paramorphism (I never thought I’d say those words).

Now recursion-schemes includes generalized versions of all of these but I’m not brave enough to try to explain them right now.

A Real Example

Before we wrap this post up, let’s demonstrate an actual useful example of recursion-schemes.

We’re going to implement trivial constant folding in a made up language I’ll call Foo.

The AST for Foo is something like

data Op = Plus | Sub | Mult | Div data Foo = Num Int -- Numeric literals | String String -- String literals | Binop Op Foo Foo -- Primitive operation | Fun String Foo -- Lambda/Abstraction over terms | App Foo Foo -- Application | Var String -- Variables deriving Show

Now we want our trivial constant folding to reduce something like Binop Plus (Num 1) (Num 2) to just Num 3. Let’s first formalize this by writing a quick little reducer

compute :: Op -> Int -> Int -> Int compute Plus = (+) compute Sub = (-) compute Mult = (*) compute Div = div reduce :: Foo -> Foo reduce (Binop op (Num a) (Num b)) = Num $ compute op a b -- The reduction reduce a = a

So we compute all constant expressions and leave everything else alone. This is pretty simple, but how can we apply it to every element in our AST? Well, time to break out recursion-schemes

data FooB a = NumB Int | StringB String | BinopB Op a a | FunB String a | App a a | Var String type instance Base Foo = FooB

And let’s rewrite reduce to use FooB instead of Foo

reduce :: Base Foo Foo -> Foo reduce (Fix (Binop op (Num a) (Num b))) = Num $ compute op a b -- The reduction reduce a = a

So this entire traversal now just becomes

constFold :: Foo -> Foo constFold = cata reduce

Now we can test our simple optimization

test = Binop Plus (Num 1) (Binop Mult (Num 2) (Num 3)) optimized = constFold test main = print test

As we’d hope, this prints out Num 7!

This seems like a lot of work but don’t forget, now that we’ve taught recursion-schemes how to do traversals, we get all of this for free. For example, let’s now write a function to grab all the free variables of an expression.

As before, let’s start by writing the simple worker function for this traversal.

freeVar :: Base Foo [String] -> [String] freeVar (NumB _) = [] freeVar (StringB _) = [] freeVar (VarB s) = [s] freeVar (BinopB _ v1 v2) = v1 ++ v2 freeVar (AppB v1 v2) = v1 ++ v2 freeVar (FunB v vs) = delete v vs

Now the full traversal is trivial!

freeIn :: Foo -> [String] freeIn = cata freeVars

As we’d hope, this traversal is much easier to write than the first one. You can imagine that the boilerplate of writing FooB and project is amortized over each traversal, making it much easier to write subsequent traversals once we’ve gone through the trouble of actually laying down the foundation.

What’s Next?

So far I’ve discussed part of the Foldable half of the recursion-schemes library. In my next post I’ll cover anamorphisms and Unfoldable, the dual of what we’ve talked about here.

<script type="text/javascript"> /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */ var disqus_shortname = 'codeco'; // required: replace example with your forum shortname /* * * DON'T EDIT BELOW THIS LINE * * */ (function() { var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true; dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq); })(); </script> <noscript>Please enable JavaScript to view the comments powered by Disqus.</noscript> comments powered by Disqus
Categories: Offsite Blogs