February 2013 - Haskell-Cafe

ANN: data-fix-cse -- Common subexpression elimination for EDSLs
by Anton Kholomiov 23 Feb '13

23 Feb '13

I'm glad to announce the package for Common subexpression elimination [1]. It's an implementation of the hashconsig algorithm as described in the paper 'Implementing Explicit and Finding Implicit Sharing in EDSLs' by Oleg Kiselyov. Main point of the library is to define this algorithm in the most generic way. You can define the AST for your DSL as fixpoint type[2]. And then all you need to use the library is to define the instance for type class `Traversable`. This idea is inspired by `data-reify` [3] package which you can use to transform your ASTs to DAGs too. But it relies on inspection of the references for values when `data-fix-cse` doesn't sacrifices the purity. A short example: Let's define a tiny DSL for signals import Data.Fix type Name = String type E = Fix Exp data Exp a = Const Double | ReadPort Name | Tfm Name [a] | Mix a a deriving (Show, Eq, Ord) We can make constant signals, read them from some ports and transform them (apply some named function to the list of signals) and mix two signals. Let's define an instance of the Traversable (hence for the Functor and Foldable) import Control.Applicative import Data.Monoid import Data.Traversable import Data.Foldable instance Functor Exp where fmap f x = case x of Const d -> Const d ReadPort n -> ReadPort n Mix a b -> Mix (f a) (f b) Tfm n as -> Tfm n $ fmap f as instance Foldable Exp where foldMap f x = case x of Mix a b -> f a <> f b Tfm n as -> mconcat $ fmap f as _ -> mempty instance Traversable Exp where traverse f x = case x of Mix a b -> Mix <$> f a <*> f b Tfm n as -> Tfm n <$> traverse f as a -> pure a Now we can use the functio `cse` cse :: (Eq<http://hackage.haskell.org/packages/archive/base/4.6.0.1/doc/html/Data-Eq.h…>(f Int<http://hackage.haskell.org/packages/archive/base/4.6.0.1/doc/html/Data-Int.…>), Ord<http://hackage.haskell.org/packages/archive/base/4.6.0.1/doc/html/Data-Ord.…>(f Int<http://hackage.haskell.org/packages/archive/base/4.6.0.1/doc/html/Data-Int.…>), Traversable<http://hackage.haskell.org/packages/archive/base/4.6.0.1/doc/html/Data-Trav…>f) => Fix<http://hackage.haskell.org/packages/archive/data-fix/0.0.1/doc/html/Data-Fi…>f -> Dag<http://hackage.haskell.org/packages/archive/data-fix-cse/0.0.1/doc/html/Dat…>f to transform our AST to DAG. DAG is already sorted. Later we can define a handy wrapper to hide the details from the client newtype Sig = Sig { unSig :: E } You can find examples in the package archive Extra-Source-Files: test/Exp.hs test/Impl.hs test/Expl.hs If you want to see a real world example of usage you can find it in the csound-expression[4]. An edsl for the Csound language. One side-note form my experience: Fixpoint types can be very flexible. It's easy to compose them. If suddenly we need to add some extra data to all cases from the example above we can easily do it with just another Functor: Imagine that we want to use a SampleRate value with all signals. Then we can do it like this: type E = Fix SampledExp data SampledExp a = SampledExp SampleRate (Exp a) then we should define an instance of the type class Traversable for our new type SampleRate. The Exp doesn't change. [1] http://hackage.haskell.org/package/data-fix-cse-0.0.1 [2] http://hackage.haskell.org/package/data-fix-0.0.1 [3] http://hackage.haskell.org/package/data-reify [4] http://hackage.haskell.org/package/csound-expression Anton

3 8

Parsec without data declarations/AST
by Sean Cormican 22 Feb '13

22 Feb '13

I have been trying to create a parser for a functional programming language, but there is no need to create an AST but merely check that the code is valid according to the grammar. In the following tutorial I have been trying to take some pointers from, data declarations are used to create an AST for the language, There is, as I understand a way to parse the language without an AST. http://www.haskell.org/haskellwiki/Parsing_a_simple_imperative_language My question is what should the type signatures for example parseFile function instead of "Stmt" accept as input if the parser is to accept Strings and numerical expressions alike ? Thanks for any help, Seán

2 4

question about: --hyperlink-source
by Doaitse Swierstra 22 Feb '13

22 Feb '13

I ran into the problem that for the packages which I install using cabal install The generated html does not contain links to the sources. This issue was raised before in: http://stackoverflow.com/questions/1587635/haddock-for-cabal-installed-modu… I have been looking into the documentation available, but could not find a way to set this e.g. as a default in some .haddock file. Am I overlooking something? Doaitse

3 2

How to input Unicode string in Haskell program?
by Semyon Kholodnov 22 Feb '13

22 Feb '13

Imagine we have this simple program: module Main(main) where main = do x <- getLine putStrLn x Now I want to run it somehow, enter "résumé 履歴書 резюме" and see this string printed back as "résumé 履歴書 резюме". Now, the first problem is that my computer runs Windows, which means that I can't use ghci ":main" or result of "ghc main.hs" to enter such an outrageous string — Windows console is locked to one specific local code page, and no codepage contains Latin-1, Cyrillic and Kanji symbols at the same time. But there is also WinGHCi. So I do ":main", copy-paste this string into the window (It works! Because Windows has Unicode for 20 years now), but the output is all messed up. In a rather curious way, actually: the input string is converted to UTF-8 byte string, and its bytes are treated as being characters from my local code page. So, it appears that I have no way to enter Unicode strings into my Haskell programs by hands, I should read them from files. That's sad, and I refuse to think I am the first one with such a problem, so I assume there is a solution/workaround. Now would someone please tell me this solution? Except from "Just stick to 127 letters of ASCII", of course.

6 6

ANNOUNCE: smallcheck-1.0
by Roman Cheplyaka 22 Feb '13

22 Feb '13

I am glad to announce a new major release of SmallCheck, a property-based testing library for Haskell. The major changes in this release are documented here: http://ro-che.info/articles/2013-02-19-smallcheck.html Roman

2 2

Is the haksell-pkg-janitors group on github alive?
by Jan Stolarek 22 Feb '13

22 Feb '13

Does anyone know if haksell-pkg-janitors group on github is alive? I've submitted a pull request a week ago but no response so far. Janek

2 2

GHC panicking when using -fext-core -O2
by Christian Gosch 21 Feb '13

21 Feb '13

Hi Cafe, when I try to create core files with the above options, ghc panics with this message: ghc: panic! (the 'impossible' happened) (GHC version 7.6.2 for x86_64-unknown-linux): make_exp (App _ (Coercion _)) Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug I tried this with 7.4.1 and with 7.6.2. Does anyone have an idea why this could happen, without looking at the code I am trying to compile? Thanks for any hint, Christian

1 0

websockets client
by Stephen Olsen 21 Feb '13

21 Feb '13

Are there any good websockets client libraries for haskell. I've been searching for one but can only come up with server implementations.

3 2

Re: [Haskell-cafe] generalized, tail-recursive left fold that can finish tne computation prematurely
by oleg＠okmij.org 21 Feb '13

21 Feb '13

As others have pointed out, _in principle_, foldr is not at all deficient. We can, for example, express foldl via foldr. Moreover, we can express head, tail, take, drop and even zipWith through foldr. That is, the entire list processing library can be written in terms of foldr: http://okmij.org/ftp/Algorithms.html#zip-folds That said, to express foldl via foldr, we need a higher-order fold. There are various problems with higher-order folds, related to the cost of building closures. The problems are especially severe in strict languages or strict contexts. Indeed, foldl_via_foldr f z l = foldr (\e a z -> a (f z e)) id l z first constructs the closure and then applies it to z. The closure has the same structure as the list -- it is isomorphic to the list. However, the closure representation of a list takes typically quite more space than the list. So, in strict languages, expressing foldl via foldr is a really bad idea. It won't work for big lists. BTW, this is why foldM is _left_ fold. The arguments against higher-order folds as a `big hammer' were made back in 1998 by Gibbons and Jones http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.1735 So, the left-fold with the early termination has a good justification. In fact, this is how Iteratees were first presented, at the DEFUN08 tutorial (part of the ICFP2008 conference). The idea of left fold with early termination is much older though. For example, Takusen (a database access framework) has been using it since 2003 or so. For a bit of history, see http://okmij.org/ftp/Streams.html#fold-stream

2 3

ANNOUNCE: mcpi-0.0.0.2 (The MineCraft-Pi API in Haskell)
by Doug Burke 21 Feb '13

21 Feb '13

I have released versions 0.0.0.1 and 0.0.0.2 (the latter being documentation improvements but it hasn't yet been built) of mcpi: http://hackage.haskell.org/package/mcpi https://github.com/DougBurke/hmcpi It is a very simple, and very incomplete, interface to MineCraft: Pi edition http://pi.minecraft.net/ Now I just need to find out how to get ghc 7.4.2 on my Raspberry Pi (oops, I mean the Raspberry Pi I told my wife I bought as a Christmas gift for the kids) so that I can use this from ghci. Any comments and improvements are more than welcome, Doug

1 0