July 2008 - Haskell-Cafe

SYB with class: Bug in Derive.hs module
by Alexey Rodriguez Yakushev 16 Sep '08

16 Sep '08

Hi people (and Ralf and Alex), I found a bug in the SYB with class library when trying to implement generic equality. I am hoping that someone in the Cafe (maybe Ralf) can confirm it is a bug, or maybe show me that I am doing something wrong. I am using the "Scrap your boilerplate with class" library (http:// homepages.cwi.nl/~ralf/syb3/). More precisely, I am using the library distributed by the HAppS project, because it works with GHC 6.8 . You can get the repository as follows: darcs get http://happs.org/HAppS/syb-with-class However, the offending module (Derive.hs) produces broken instances in both distributions. The bug: ---------- Generic equality needs type safe casting when implemented in SYB3, I have tried both the gzipwith variant and using Pack datatypes (geq*.hs in the first distribution). However, both functions loop when applied to a tree value. This loop occurs when the functions try to cast one of the arguments. I have managed to reduce the error to a smaller source file that I send attached. It does the following: > main = print typeReps > > tree = (Bin (Leaf 1) (Leaf 2))::BinTree Int > > data Pack = forall x. Typeable x => Pack x > > packedChildren = gmapQ geqCtx Pack tree > > typeOfPack (Pack x) = typeOf x > > typeReps = map typeOfPack packedChildren Basically the tree is transformed into a list of Pack-ed values and then to a list of type representations. This program loops at "typeOf" when you call "main". The Data instance that Derive generates is as follows: > instance (Data ctx a, > Data ctx (BinTree a), > Sat (ctx (BinTree a))) => > Data ctx (BinTree a) where Note the recursive |Data ctx (BinTree a)| in the context. If I get rid of it (a correct manual instance is also included in the attachment) the example works. I thought of removing this from the context in the Derive source. But maybe I might break some other use cases. So I am asking for help! Should Derive be fixed? How? Cheers, Alexey

3 2

Arrow without `>>>'
by Valery V. Vorotyntsev 03 Sep '08

03 Sep '08

Hi, friends, I've built GHC from darcs, and... Could anybody tell me, what's the purpose of Arrow[1] not having `>>>' method? 1. http://darcs.haskell.org/packages/base/Control/Arrow.hs $ ghci GHCi, version 6.9.20080104: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> :m + Control.Arrow Prelude Control.Arrow> :i Arrow class (Control.Category.Category a) => Arrow a where arr :: (b -> c) -> a b c pure :: (b -> c) -> a b c first :: a b c -> a (b, d) (c, d) second :: a b c -> a (d, b) (d, c) (***) :: a b c -> a b' c' -> a (b, b') (c, c') (&&&) :: a b c -> a b c' -> a b (c, c') -- Defined in Control.Arrow instance Arrow (->) -- Defined in Control.Arrow instance (Monad m) => Arrow (Kleisli m) -- Defined in Control.Arrow Prelude Control.Arrow> Leaving GHCi. I can't build[2] arrows-0.3 package without `>>>' in Arrow. 2. vvv@fun:~/src/arrows$ darcs w { hunk ./Control/Arrow/Operations.hs 36 +import Control.Category ((>>>)) hunk ./Control/Arrow/Transformer/CoState.hs 23 +import Control.Category ((>>>)) } vvv@fun:~/src/arrows$ runhaskell Setup build Preprocessing library arrows-0.3... Building arrows-0.3... [ 3 of 12] Compiling Control.Arrow.Transformer.CoState ( Control/Arrow/Transformer/CoState.hs, dist/build/Control/Arrow/Transformer/CoState.o ) Control/Arrow/Transformer/CoState.hs:29:7: `>>>' is not a (visible) method of class `Arrow' The question arises "should I?", but this is one of lambdabot's[3] depencies. 3. http://code.haskell.org/lambdabot/ Thanks a lot! -- vvv

3 3

Galois Tech Talks: Stream Fusion for Haskell Arrays
by Don Stewart 28 Aug '08

28 Aug '08

Just a quick note about next week's Galois Tech Talk. Now that Galois has completed its move into downtown Portland, and a shiny new, centrally located, office space, we're opening up our tech talk series a bit more widely. If you're in Portland, and interested in functional programming and formal methods, drop by! ------------------------------------------------------------------------ Title: Stream Fusion for Haskell Arrays Speaker: Don Stewart Date: Tuesday, July 15th, 10.30am sharp. Location: Galois, Inc. 421 SW 6th Ave. Suite 300 (3rd floor of the Commonwealth Building) Portland, Oregon Abstract: Arrays have traditionally been an awkward data structure for Haskell programmers. Despite the large number of array libraries available, they have remained relatively awkward to use in comparison to the rich suite of purely functional data structures, such as fingertrees or finite maps. Arrays have simply not been first class citizens in the language. In this talk we'll begin with a survey of the more than a dozen array types available, including some new matrix libraries developed in the past year. I'll then describe a new efficient, pure, and flexible array library for Haskell with a list like interface, based on work in the Data Parallel Haskell project, that employs stream fusion to dramatically reduce the cost of pure arrays. The implementation will be presented from the ground up, along with a discussion of the entire compilation process of the library, from source to assembly. About the Galois Tech Talks. Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities. The talks are open and free. If you’re planning to attend, dropping a note to <dons(a)galois.com> is appreciated, but not required. If you're interested in giving a talk, Don's always looking for new speakers. ------------------------------------------------------------------------

4 7

Associative Commutative Unification
by John D. Ramsdell 27 Aug '08

27 Aug '08

I'd like to write an obviously correct implementation of a unifier, a program that when given two terms, finds a substitution that makes the two terms equal. The phrase "obviously correct" is meant to imply that the clarity of the code trumps efficiency. As near as I can tell, high performance unifiers are full of side-effects, and achieving the same performance without side-effects in Haskell is difficult or impossible. In contrast, it is easy to write obviously correct Hasklell implementations of unifiers for freely generated term algebras. One can use Lawrence Paulson's code in ML for the Working Programmer as a template or follow Martelli and Montanari's simple set of rules. My problem is one of my operators is multiplication, which is associative and commutative. These two properties make unification much more difficult. Mark Stickel described a complete unification algorithm for this problem, but the task of translating his description into an obviously correct Haskell program appears to be difficult. For example, the algorithm requires the generation of the basis of solutions to linear homogeneous diophantine equations. I haven't located an algorithm for this part yet. If you have experience implemented equational unification in Haskell, please share it. John

6 9

CouchDB module in Yhc source tree: clarification, and small problems with other packages
by Dimitry Golubovsky 21 Aug '08

21 Aug '08

Hi, Don asked: > Are we likely to see the couchdb bindings released as a standalone > library for the wider community? Let me explain a little bit why the CouchDB module appears in the Yhc repo. As the next stage of the Yhc/Javascript project, I am trying to set up a web service where people might upload some Haskell code (or reference to such code, these details haven't been clarified yet), and get it compiled by background Yhc/ycr2js batch job, returning a HTML page with Javascript in response. CouchDB was picked* as intermediate storage for this project. Therefore an interface module was needed, so I wrote one. This module, `Database.CouchDB' is not 100% finished; it was coded up to satisfy the needs of the first utility I wrote, `cdbup' which is currently capable of uploading a text (utf-8 expected) or a binary file as a document attachment to CouchDB. So some functionality hasn't been coded yet, although it will definitely be, as the project develops. Regarding packaging, I hope I will eventually put it on Hackage, but there are some problems with another packages which I'll try to explain here, so maybe those packages' developers suggest something. 1. Text.JSON. This module was picked from Jun Mukai's haskellnet package (http://darcs.haskell.org/SoC/haskellnet/) One problem with this package, it needs too many dependencies (while JSON module relies only on Packrat parser). I had to extract the JSON module into Yhc tree; can the haskellnet package be split somehow into orthogonal sub-packages, and maybe one toplevel package which would pull all parts together if used? 2. Text.JSON again. I had to change the pNumber function (parser for numeric nodes) replacing the '1'..'9' digits range with '0' .. '9'. Otherwise it did not handle JSON-encoded numbers equal to zero. I am not sure I was 100% right, so perhaps some JSON experts here might correct me. 3. Packrat parser does not seem to be packaged anywhere else, does it? 4. The dataenc package (http://code.haskell.org/dataenc/devo/) from which I pulled the Codec.Binary.Base64 module. The package may need some adjustment to GHC 6.8.x packages structure as only "base" listed in build-depends does not seem to be enough: when building it, Cabal complains for hidden packages such as collections (which I had to add manually to the cabal file), etc. Is it some problem with my GHC setup, or does just the dataenc.cabal need to be updated? So, in order to get things done quicker, I pulled the said pieces from their packages into Yhc tree. For packaging the CouchDB interface, definitely these duplicates need to be removed. Other packages that CouchDB relies upon, are**: base, network, HTTP, filepath, base64-string, utf8-string Thanks for the interest in CouchDB interface, and feel free to ask any questions. --- * before support form IBM/Apache was announced, but this recent development definitely increases interest to CouchDB ** Just from the -package options I used to compile it; I may have something omitted here. -- Dimitry Golubovsky Anywhere on the Web

5 5

Anglo Haskell 2008
by Matthew Sackman 11 Aug '08

11 Aug '08

Anglo Haskell is a gathering of all people Haskell-related from beginners, to seasoned hackers to academic giants. All and more are welcomed by large fuzzy green lambdas. Anglo Haskell has happened for the last two years and we see no reason why it should not happen again this year. For the last two years they've tended to have talks on Fridays and then Other Things on the Saturday (including Punting and Group Hacking, some or more of which may have happened in Pubs). We're proposing the same general format this year. In contrast to the last two years which have been held at MSR Cambridge (UK), we're this year proposing to hold the event at Imperial College, London. London is probably easier to get to and from (though more tedious to get across) than Cambridge and we hope this will attract people who previously have not been able to get out to Cambridge. The proposed dates are Friday the 8th and Saturday the 9th of August. More details are available on the wikipage: http://www.haskell.org/haskellwiki/AngloHaskell/2008 Please feel free to add to this page. If you're at all interested in coming along then please add your name to the wikipage. If you're interested in giving a talk - on literally anything Haskell related: this is not a solely theory day or solely a practical day; anything goes which is Haskell related - then similarly add yourself to the list of speakers. Schedule and other details will be confirmed soon. Lodging, travel and all other related matters will be discussed on the irc channel (and will eventually migrate to the wikipage) #anglohaskell. If you're free that weekend then please come along! Also, if you'd really like to come but can't make those dates and there are many of you then please shout loudly and things could potentially be moved, though with the lack of time left before the event, we'd prefer to avoid this. Matthew

1 4

Cabal + yi + alex problem.
by Yann Golanski 02 Aug '08

02 Aug '08

I cannot seem to be able to install yi via cabal install. The error I get is as follows. I suspect alex is not installed in the correct place. ; sudo cabal install yi Resolving dependencies... Downloading yi-0.4.3... Configuring yi-0.4.3... cabal: alex version >=2.0.1 && <3 is required but it could not be found. cabal: Error: some packages failed to install: yi-0.4.3 failed during the configure step. The exception was: exit: ExitFailure 1 ; sudo cabal install alex Resolving dependencies... Downloading alex-2.2... [1 of 1] Compiling Main ( Setup.lhs, dist/setup/Main.o ) Linking dist/setup/setup ... Warning: defaultUserHooks in Setup script is deprecated. Configuring alex-2.2... Warning: No 'build-type' specified. If you do not need a custom Setup.hs or ./configure script then use 'build-type: Simple'. Preprocessing executables for alex-2.2... Building alex-2.2... [...] Linking dist/build/alex/alex ... Installing: /home/yann/.cabal/bin ; sudo cabal install yi Resolving dependencies... 'yi-0.4.3' is cached. Configuring yi-0.4.3... cabal: alex version >=2.0.1 && <3 is required but it could not be found. cabal: Error: some packages failed to install: yi-0.4.3 failed during the configure step. The exception was: exit: ExitFailure 1 -- yann(a)kierun.org -= H+ =- www.kierun.org PGP: 009D 7287 C4A7 FD4F 1680 06E4 F751 7006 9DE2 6318

6 9

How can I get the mutable array out of an IOUArray for FFI use?
by Ryan Ingram 02 Aug '08

02 Aug '08

I wrote some fast bit-twiddling functions in C because my Haskell performance wasn't good enough. Now I'm trying to recompile with GHC6.8.3 and failing. This code worked on GHC6.6.1. I get the following error: > ghc --make main.hs Bitmap.hs:11:7: Could not find module `Data.Array.IO.Internals': it is hidden (in package array-0.1.0.0) I suppose I can declare a copy of the internal type and use unsafeCoerce#, but that seems like a terrible idea if there is a better way. What's the right way to make this work? Can I force that module to be unhidden? Should I file a GHC bug? -- ryan {-# OPTIONS_GHC -fffi -fglasgow-exts #-} {-# INCLUDE "bitmap_operations.h" #-} module Bitmap ( clearBitmap, ) where import Foreign.Ptr import Data.Array.Base import Data.Array.IO.Internals import GHC.Exts import Data.Word foreign import ccall unsafe clear_bitmap :: MutableByteArray# RealWorld -> Word32 -> Word32 -> IO () {-# INLINE unsafeGetMutableArray# #-} unsafeGetMutableArray# :: IOUArray Int Word32 -> MutableByteArray# RealWorld unsafeGetMutableArray# (IOUArray (STUArray _ _ array#)) = array# clearBitmap :: IOUArray Int Word32 -> Word32 -> Word32 -> IO () clearBitmap a1 color size = clear_bitmap (unsafeGetMutableArray# a1) color size

2 1

Using fundeps to resolve polymorphic types to concrete types
by Bryan Donlan 02 Aug '08

02 Aug '08

Hi, Is there any theoretical reason that functional dependencies can't be used to resolve a polymorphic type to a concrete type? For example: > -- compile with -fglasgow-exts > > class DeriveType a b | a -> b > > data A = A > data B = B > > instance DeriveType A B > > simpleNarrow :: DeriveType A b => b -> B > simpleNarrow = id Since 'b' is uniquely determined by the fundep in DeriveType, it seems that this ought to work; ie, since the only type equation satisfying DeriveType A b is B -> B, it should reduce to that before trying to fit its type against its body. The motivation is this case: > data ComplexType a where > SomeConstructor :: DeriveType a b => a -> b -> ComplexType a > > specialCaseFunc :: ComplexType A -> B > specialCaseFunc (SomeConstructor _ b) = b Essentially, if I have a data structure with two types used as fields, and one uniquely determines the other, I'd like to use these instances to avoid re-stating the implied one in the type equations, if possible. Is there some theoretical reason for this not to work, or is it just a limitation of GHC's current implementation? (Note, I'm testing with GHC 6.8.2, so it's possible this might be fixed in trunk already...) Thanks, Bryan Donlan

5 9

Cabal files on Windows
by John Lato 01 Aug '08

01 Aug '08

Hello, Can anyone point me to a method for including path names with spaces in a cabal file? I would like to add a line similar to the following: include-dirs: C:\Program Files\program\include and of course a corresponding library as well. I've tried various methods of escaping the space and quoting, and nothing seems to work. Is this possible at all? I'm using Cabal-1.2.4.0 on Windows. I've tried running with a Windows shell and MSYS bash, with the same results. Thanks, John Lato

4 8