News aggregator

ICFP recordings

Haskell on Reddit - Thu, 09/03/2015 - 1:22am
Categories: Incoming News

Examples for Control.Lens.Plated?

haskell-cafe - Thu, 09/03/2015 - 12:44am
Hello Cafe, I'm considering porting some of my code that uses uniplate to lens. But Control.Lens.Plated is giving me headaches. So I'm looking for remedy. Has anyone used it and willing to share examples? I hope that seeing some of the combinators in action would help me understand the type signatures and documentation. What I'm particularly interested in is the following: 1) implementation of something like transformBi and rewriteBi using lens 2) usage of *On, *Off and *OnOff combinators (e.g., transformMOn, transformMOff, transformMOnOff). What I want to understand is the difference between the 3 variants. Also, what does it mean to "Transform every element in the tree in a region indicated by a supplied Traversal" and how exactly does the traversal define the region. 3) any recursive tree traversals/transformations using Plated that stop the recursion at a certain point (e.g., upon seeing a certain constructor) I hope this isn't too vague, but, please, let me know if it is. /Andrey
Categories: Offsite Discussion

Flag to recompile modules which had warnings

haskell-cafe - Wed, 09/02/2015 - 7:44pm
This is a call for comments before I'd create a ticket in corresponding project (I'm not sure if it should be ghc or stack/cabal). There's a common situation I get into: I compile with "stack build" (or cabal build), get a big list of warnings, fix few of them, then I re-compile project, but a lot of warnings are gone now. The only option I'm left with is to use "-fforce-recomp". Problems with -fforce-recomp are: - full-recompile is quite long for big projects - most people don't know about it, especially newbies I think some flag, which would be turned on by default, which would indicate to "recompile modules if they previously had warnings" would be awesome to have. 1. would you like to have that flag? 2. would you like it "on" by default? 3. should ticket go into ghc or stack/cabal-install project? Thank you. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >
Categories: Offsite Discussion

Question about Snap + Heist + Static Pages

Haskell on Reddit - Wed, 09/02/2015 - 7:39pm

A common use case for Apache + PHP is for simple static sites where you just need to do simple sharing of html fragments (like the header and footer). Is there an example anywhere of using snap and heist to do this? In fact, it could just be wai instead of snap (but I believe that it's more likely that someone has done this with snap). Specifically, what I am looking for is a way to set things up such that I have a directory with heist templates, and routing just takes the path from the URL, and uses it for a template lookup. That's it. No database, no persistence, no auth. I thought that snap init might give me enough to figure this out, but it didn't. I would appreciate any help. Thanks.

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

Roman Cheplyaka: MonadFix example: compiling regular expressions

Planet Haskell - Wed, 09/02/2015 - 2:00pm
{-# LANGUAGE RecursiveDo, BangPatterns #-} import Control.Applicative import Data.Function (fix) import Data.IntMap as IntMap import Control.Monad.Fix (mfix) import Control.Monad.Trans.State import Control.Monad.Trans.Class (lift) import Text.Read (readMaybe)

MonadFix is an odd beast; many Haskell programmers will never use it in their careers. It is indeed very rarely that one needs MonadFix; and for that reason, non-contrived cases where MonadFix is needed are quite interesting to consider.

In this article, I’ll introduce MonadFix and show how it can be handy for compiling the Kleene closure (also known as star or repetition) of regular expressions.

What is MonadFix?

If you hear about MonadFix for the first time, you might think that it is needed to define recursive monadic actions, just like ordinary fix is used to define recursive functions. That would be a mistake. In fact, fix is just as applicable to monadic actions as it is to functions:

guessNumber m = fix $ \repeat -> do putStrLn "Enter a guess" n <- readMaybe <$> getLine if n == Just m then putStrLn "You guessed it!" else do putStrLn "You guessed wrong; try again" repeat

So, what is mfix for? First, recall that in Haskell, one can create recursive definitions not just for functions (which makes sense in other, non-lazy languages) or monadic actions, but for ordinary data structures as well. This is known as cyclic (or circular, or corecursive) definitions; and the technique itself is sometimes referred to as tying the knot.

The classic example of a cyclic definition is the (lazy, infinite) list of Fibonacci numbers:

fib = 0 : 1 : zipWith (+) fib (tail fib)

Cyclic definitions are themselves rare in day-to-day Haskell programming; but occasionally, the right hand side will be not a pure value, but a monadic computation that needs to be run in order to obtain the value.

Consider this (contrived) example, where we start the sequence with an arbitrary number entered by the user:

fibIO1 = do putStrLn "Enter the start number" start <- read <$> getLine return $ start : 1 : zipWith (+) fibIO1 (tail fibIO1)

This doesn’t typecheck because fibIO is not a list; it’s an IO action that produces a list.

But if we try to run the computation, it doesn’t make much sense either:

fibIO2 = do putStrLn "Enter the start number" start <- read <$> getLine fib <- fibIO2 return $ start : 1 : zipWith (+) fib (tail fib)

This version of fibIO will ask you to enter the start number ad infinitum and never get to evaluating anything.

Of course, the simplest thing to do would be to move IO out of the recursive equation; that’s why I said the example was contrived. But MonadFix gives another solution:

fibIO3 = mfix $ \fib -> do putStrLn "Enter the start number" start <- read <$> getLine return $ start : 1 : zipWith (+) fib (tail fib)

Or, using the do-rec syntax:

fibIO4 = do rec fib <- do putStrLn "Enter the start number" start <- read <$> getLine return $ start : 1 : zipWith (+) fib (tail fib) return fib Compiling regular expressions

As promised, I am going to show you an example usage of MonadFix that solved a problem other than “how could I use MonadFix?”. This came up in my work on regex-applicative.

For a simplified presentation, let’s consider this type of regular expressions:

data RE = Sym Char -- symbol | Seq RE RE -- sequence | Alt RE RE -- alternative | Rep RE -- repetition

Our goal is to compile a regular expression into a corresponding NFA. The states will be represented by integer numbers. State 0 corresponds to successful completion; and each Sym inside a regex will have a unique positive state in which we are expecting the corresponding character.

type NFAState = Int

The NFA will be represented by a map

type NFA = IntMap (Char, [NFAState])

where each state is mapped to the characters expected at that state and the list of states where we go in case we get the expected character.

To compile a regular expression, we’ll take as an argument the list of states to proceed to when the regular expression as a whole succeeds (otherwise we’d have to compile each subexpression separately and then glue NFAs together). This is essentially the continuation-passing style; only instead of functions, our continuations are NFA states.

During the compilation, we’ll use a stack of two State monads: one to assign sequential state numbers to Syms; the other to keep track of the currently constructred NFA.

-- Returns the list of start states and the transition table compile :: RE -> ([NFAState], NFA) compile re = runState (evalStateT (go re [0]) 0) IntMap.empty -- go accepts exit states, returns entry states go :: RE -> [NFAState] -> StateT NFAState (State NFA) [NFAState] go re exitStates = case re of Sym c -> do !freshState <- gets (+1); put freshState lift $ modify' (IntMap.insert freshState (c, exitStates)) return [freshState] Alt r1 r2 -> (++) <$> go r1 exitStates <*> go r2 exitStates Seq r1 r2 -> go r1 =<< go r2 exitStates

This was easy so far: alternatives share their exit states and their entry states are combined; and consequtive subexpressions are chained. But how do we compile Rep? The exit states of the repeated subexpression should become its own entry states; but we don’t know the entry states until we compile it!

And this is precisely where MonadFix (or recursive do) comes in:

Rep r -> do rec let allEntryStates = ownEntryStates ++ exitStates ownEntryStates <- go r allEntryStates return allEntryStates

Why does this circular definition work? If we unwrap the State types, we’ll see that the go function actually computes a triple of three non-strict fields:

  1. The last used state number
  2. The list of entry states
  3. The NFA map

The elements of the triple may depend on each other as long as there are no actual loops during evaluation. One can check that the fields can be indeed evaluated linearly in the order in which they are listed above:

  1. The used state numbers at each step depend only on the regular expression itself, so it can be computed wihtout knowing the other two fields.
  2. The list of entry states relies only on the state number information; it doesn’t need to know anything about the NFA transitions.
  3. The NFA table needs to know the entry and exit states; but that is fine, we can go ahead and compute that information without creating any reverse data dependencies.
Further reading

An ASM Monad – a similar example from a different domain.

Oliver Charles’s 24 Days of GHC Extensions: Recursive Do.

Levent Erkok’s thesis which contains all you need to know about MonadFix, including several other examples.

Todd Wilson points out that Douglas McIlroy describes a similar regular expression compilation technique in his 2004 JFP Functional Pearl Enumerating the strings of regular languages. Like this article, Douglas’s paper uses a circular definition when compiling the Kleene closure. But the circular definition is not monadic there: instead of using the State monad, Douglas passes the state around by hand.

Categories: Offsite Blogs

JOB OPPORTUNITY_ IT Software Developer

haskell-cafe - Wed, 09/02/2015 - 11:40am
CREATE-NET is seeking a Software Developer passionate about web applications development and its latest technologies. You will be part of our Innovation IT team based in Trento, Italy and will contribute to the development and testing of our portfolio of specialized software products for supporting the promotion and education of Create-Net innovation result. *Technical skills* ● Working experience with HTML5, CSS, AJAX, JSON APIs, JavaScript ● Working experience with Ruby (on Rails) and PHP plus some knowledge about Java and Node.js ● Knowledge of Mobile application development (Native Android/iOs or PhoneGap/Cordova) and Responsive Web Design ● Knowledge or interest of functional programming languages (Haskell, Common Lisp, others) will be considered a strong plus ● Experience with relational DBMSs (PostgreSQL in particular) ● Experience with distributed version control systems such as Git ● Familiarity working with Linux environments (Redhat, Ubuntu) ●
Categories: Offsite Discussion

JOB OPPORTUNITY_ Jr. Functional Software Developer

haskell-cafe - Wed, 09/02/2015 - 11:40am
CREATE-NET is seeking a motivated Junior Functional Software Developer. You will be part our innovation IT team based in Trento, Italy, and will be contributing to the development and testing of our specialized software products which support the workflow related to scientific content organization. *Technical skills* ● Experience with one or more functional programming languages. Haskell and Common Lisp are preferable. ● Experience with web technologies: Javascript, HTML5, CSS, AJAX, JSON APIs, web services, responsive web design. ● Optional knowledge of either Node.js, Ruby on Rails, PHP, Java is considered a plus ● Experience with relational DBMSs (PostgreSQL) ● Experience with distributed version control systems (Git) ● Familiarity in working with GNU/Linux environments (RHEL, Ubuntu, etc.) *Specific job responsibilities will include* ● Contributing to the maintenance and the improvement of our content management platforms and appl
Categories: Offsite Discussion

Speaker list available for Haskell eXchange conference, also announcing 2-day Hackathon (and promo code inside!)

Haskell on Reddit - Wed, 09/02/2015 - 11:30am

Hey everyone!

The programme for Haskell eXchange in London Oct 8th-9th, is finally getting settled, we'll have 4 keynotes over the two days from Simon Peyton Jones, Lennart Augustsson, Simon Marlow and Luite Stegeman!

To check out the full list of speakers and their topics, go here:

Descriptions for some of the keynotes are still missing, hopefully it will be updated soon.

We're also announcing that there's going to be a 2-day Hackathon over the following weekend where the focus will be on improving the Haskell infrastructure, anyone should feel free to come and if you're a beginner that wants to start contributing to the Haskell infrastructure, you'll be able to get help from experienced contributors.

Read the full description and register here (it's free):

Finally, if you want to get 25% off on the conference ticket, you can use the promo code HASKELL-EXCHANGE-25, it should be valid until September 12th!

Hope to see you all there! :)

submitted by frolsen
[link] [7 comments]
Categories: Incoming News

Wolfgang Jeltsch: MIU in Haskell

Planet Haskell - Wed, 09/02/2015 - 8:05am

In the Theory Lunch of the last week, James Chapman talked about the MU puzzle from Douglas Hofstadter’s book Gödel, Escher, Bach. This puzzle is about a string rewriting system. James presented a Haskell program that computes derivations of strings. Inspired by this, I wrote my own implementation, with the goal of improving efficiency. This blog post presents this implementation. As usual, it is available as a literate Haskell file, which you can load into GHCi.

The puzzle

Let me first describe the MU puzzle shortly. The puzzle deals with strings that may contain the characters , , and . We can derive new strings from old ones using the following rewriting system:

The question is whether it is possible to turn the string into the string using these rules.

You may want to try to solve this puzzle yourself, or you may want to look up the solution on the Wikipedia page.

The code

The code is not only concerned with deriving from , but with derivations as such.


We import Data.List:

import Data.List Basic things

We define the type Sym of symbols and the type Str of symbol strings:

data Sym = M | I | U deriving Eq type Str = [Sym] instance Show Sym where show M = "M" show I = "I" show U = "U" showList str = (concatMap show str ++)

Next, we define the type Rule of rules as well as the list rules that contains all rules:

data Rule = R1 | R2 | R3 | R4 deriving Show rules :: [Rule] rules = [R1,R2,R3,R4] Rule application

We first introduce a helper function that takes a string and returns the list of all splits of this string. Thereby, a split of a string str is a pair of strings str1 and str2 such that str1 ++ str2 == str. A straightforward implementation of splitting is as follows:

splits' :: Str -> [(Str,Str)] splits' str = zip (inits str) (tails str)

The problem with this implementation is that walking through the result list takes quadratic time, even if the elements of the list are left unevaluated. The following implementation solves this problem:

splits :: Str -> [(Str,Str)] splits str = zip (map (flip take str) [0 ..]) (tails str)

Next, we define a helper function replace. An expression replace old new str yields the list of all strings that can be constructed by replacing the string old inside str by new.

replace :: Str -> Str -> Str -> [Str] replace old new str = [front ++ new ++ rear | (front,rest) <- splits str, old `isPrefixOf` rest, let rear = drop (length old) rest]

We are now ready to implement the function apply, which performs rule application. This function takes a rule and a string and produces all strings that can be derived from the given string using the given rule exactly once.

apply :: Rule -> Str -> [Str] apply R1 str | last str == I = [str ++ [U]] apply R2 (M : tail) = [M : tail ++ tail] apply R3 str = replace [I,I,I] [U] str apply R4 str = replace [U,U] [] str apply _ _ = [] Derivation trees

Now we want to build derivation trees. A derivation tree for a string str has the following properties:

  • The root is labeled with str.
  • The subtrees of the root are the derivation trees for the strings that can be generated from str by a single rule application.
  • The edges from the root to its subtrees are marked with the respective rules that are applied.

We first define types for representing derivation trees:

data DTree = DTree Str [DSub] data DSub = DSub Rule DTree

Now we define the function dTree that turns a string into its derivation tree:

dTree :: Str -> DTree dTree str = DTree str [DSub rule subtree | rule <- rules, subStr <- apply rule str, let subtree = dTree subStr] Derivations

A derivation is a sequence of strings with rules between them such that each rule takes the string before it to the string after it. We define types for representing derivations:

data Deriv = Deriv [DStep] Str data DStep = DStep Str Rule instance Show Deriv where show (Deriv steps goal) = " " ++ concatMap show steps ++ show goal ++ "\n" showList derivs = (concatMap ((++ "\n") . show) derivs ++) instance Show DStep where show (DStep origin rule) = show origin ++ "\n-> (" ++ show rule ++ ") "

Now we implement a function derivs that converts a derivation tree into the list of all derivations that start with the tree’s root label. The function derivs traverses the tree in breadth-first order.

derivs :: DTree -> [Deriv] derivs tree = worker [([],tree)] where worker :: [([DStep],DTree)] -> [Deriv] worker tasks = rootDerivs tasks ++ worker (subtasks tasks) rootDerivs :: [([DStep],DTree)] -> [Deriv] rootDerivs tasks = [Deriv (reverse revSteps) root | (revSteps,DTree root _) <- tasks] subtasks :: [([DStep],DTree)] -> [([DStep],DTree)] subtasks tasks = [(DStep root rule : revSteps,subtree) | (revSteps,DTree root subs) <- tasks, DSub rule subtree <- subs]

Finally, we implement the function derivations which takes two strings and returns the list of those derivations that turn the first string into the second:

derivations :: Str -> Str -> [Deriv] derivations start end = [deriv | deriv@(Deriv _ goal) <- derivs (dTree start), goal == end]

You may want to enter

derivations [M,I] [M,U,I]

at the GHCi prompt to see the derivations function in action. You can also enter

derivations [M,I] [M,U]

to get an idea about the solution to the MU puzzle.

Tagged: Douglas Hofstadter, functional programming, Gödel, Escher, Bach (book), Haskell, Institute of Cybernetics, James Chapman, literate programming, MU puzzle, string rewriting, talk, Theory Lunch
Categories: Offsite Blogs

Wolfgang Jeltsch: MIU in Curry

Planet Haskell - Wed, 09/02/2015 - 8:00am

More than two years ago, my colleague Denis Firsov and I gave a series of three Theory Lunch talks about the MIU string rewriting system from Douglas Hofstadter’s MU puzzle. The first talk was about a Haskell implementation of MIU, the second talk was an introduction to the functional logic programming language Curry, and the third talk was about a Curry implementation of MIU. The blog articles MIU in Haskell and A taste of Curry are write-ups of the first two talks. However, a write-up of the third talk has never seen the light of day so far. This is changed with this article.

As usual, this article is written using literate programming. The article source is a literate Curry file, which you can load into KiCS2 to play with the code.

I want to thank all the people from the Curry mailing list who have helped me improving the code in this article.


We import the module SearchTree:

import SearchTree Basic things

We define the type Sym of symbols and the type Str of symbol strings:

data Sym = M | I | U showSym :: Sym -> String showSym M = "M" showSym I = "I" showSym U = "U" type Str = [Sym] showStr :: Str -> String showStr str = concatMap showSym str

Next, we define the type Rule of rules:

data Rule = R1 | R2 | R3 | R4 showRule :: Rule -> String showRule R1 = "R1" showRule R2 = "R2" showRule R3 = "R3" showRule R4 = "R4"

So far, the Curry code is basically the same as the Haskell code. However, this is going to change below.

Rule application

Rule application becomes a lot simpler in Curry. In fact, we can code the rewriting rules almost directly to get a rule application function:

applyRule :: Rule -> Str -> Str applyRule R1 (init ++ [I]) = init ++ [I, U] applyRule R2 ([M] ++ tail) = [M] ++ tail ++ tail applyRule R3 (pre ++ [I, I, I] ++ post) = pre ++ [U] ++ post applyRule R4 (pre ++ [U, U] ++ post) = pre ++ post

Note that we do not return a list of derivable strings, as we did in the Haskell solution. Instead, we use the fact that functions in Curry are nondeterministic.

Furthermore, we do not need the helper functions splits and replace that we used in the Haskell implementation. Instead, we use the ++-operator in conjunction with functional patterns to achieve the same functionality.

Now we implement a utility function applyRules for repeated rule application. Our implementation uses a similar trick as the famous Haskell implementation of the Fibonacci sequence:

applyRules :: [Rule] -> Str -> [Str] applyRules rules str = tail strs where strs = str : zipWith applyRule rules strs

The Haskell implementation does not need the applyRules function, but it needs a lot of code about derivation trees instead. In the Curry solution, derivation trees are implicit, thanks to nondeterminism.


A derivation is a sequence of strings with rules between them such that each rule takes the string before it to the string after it. We define types for representing derivations:

data Deriv = Deriv [DStep] Str data DStep = DStep Str Rule showDeriv :: Deriv -> String showDeriv (Deriv steps goal) = " " ++ concatMap showDStep steps ++ showStr goal ++ "\n" showDerivs :: [Deriv] -> String showDerivs derivs = concatMap ((++ "\n") . showDeriv) derivs showDStep :: DStep -> String showDStep (DStep origin rule) = showStr origin ++ "\n-> (" ++ showRule rule ++ ") "

Now we implement a function derivation that takes two strings and returns the derivations that turn the first string into the second:

derivation :: Str -> Str -> Deriv derivation start end | start : applyRules rules start =:= init ++ [end] = Deriv (zipWith DStep init rules) end where rules :: [Rule] rules free init :: [Str] init free

Finally, we define a function printDerivations that explicitly invokes a breadth-first search to compute and ultimately print derivations:

printDerivations :: Str -> Str -> IO () printDerivations start end = do searchTree <- getSearchTree (derivation start end) putStr $ showDerivs (allValuesBFS searchTree)

You may want to enter

printDerivations [M, I] [M, I, U]

at the KiCS2 prompt to see the derivations function in action.

Tagged: breadth-first search, Curry, Denis Firsov, Douglas Hofstadter, functional logic programming, functional pattern, functional programming, Haskell, Institute of Cybernetics, KiCS2, literate programming, logic programming, MU puzzle, string rewriting, talk, Theory Lunch
Categories: Offsite Blogs

screencasts/video tutorials

Haskell on Reddit - Wed, 09/02/2015 - 5:13am

hi, i am really interested in learning Haskell. can you recommend something good video tutorials/screencasts where there is a project/product not only basic syntax.

submitted by Cosaquee
[link] [3 comments]
Categories: Incoming News

What's the best way to get a CLI+Haskell environment on Windows

Haskell on Reddit - Wed, 09/02/2015 - 5:07am

I have some CLI tools developped in Haskell, that I need some of my college at work to use. He doesn't know anything about programming and even command line, but the only things he will need to do , is build the tool (I can help him), modifies some configuration file , launch the tool and open the result in Excel.

I was thinking first of using Docker, but he need to open the file on Excel. My experience with Docker on Mac is that it's a bit of pain to share files between a container and the Mac. Is it the same on windows ?

Otherwise I was thinking stack would be a good solution (as it seems to also install ghc). However, AFAIR using the command line on Windows is not great. Could I use cygwin and stack on windows ?

What would you recommend ?

submitted by maxigit
[link] [24 comments]
Categories: Incoming News

Is there a reason some GHC extensions not to be used by default in new GHC versions?

Haskell on Reddit - Wed, 09/02/2015 - 2:13am

For example OverloadedStrings, BangPattern, MultiWayIf, LambdaCase, etc. I think that there are extensions that will not hurt much old software and they could be disabled for old compilations. But this could improve new versions of GHC and give some direction.

submitted by varosi
[link] [17 comments]
Categories: Incoming News