- Haskell-Cafe - Haskell.org

Annotaing abstract syntax trees
by José Romildo Malaquias 09 May '12

09 May '12

Hello. I am reading Martijn's MSc Thesis "Generic Selections of Subexpressions", where one can found some discussions about annotating abstract syntax trees (AST). In order to follow the discussion I wrote the attached Haskell program, which is an interpreter for an simple typed expression language. The Annotations package is used. The expression pattern is represented by a single recursive data type. Annotations are used for positions in the input source, and also for the type of expressions and subexpressions. I would like somebody to review the code and comment on it, as I am not sure I am using the concepts right. Also I would like the type checker to produce an expression annotated with both positions and calculated types. Currently it discards the position annotations. Any sugestions on how to modify it is welcome. Next step is adding a new form of expression to introduce local variable bindings. After that I want to start working with ASTs represented by mutually recursive data types. Then I will need multirec... Romildo

2 1

Re: [Haskell-cafe] Un-memoization
by oleg＠okmij.org 09 May '12

09 May '12

Victor Miller wrote: > I was writing a Haskell program which builds a large labeled binary tree > and then does some processing of it, which is fold-like. In the actual > application that I have in mind the tree will be *huge*. If the whole tree > is kept in memory it would probably take up 100's of gigabytes. Because of > the pattern of processing the tree, it occurred to me that it might be > better (cause much less paging) if some large subtrees could be replaced by > thunks which can either recalculate the subtree as needed, or write out the > subtree, get rid of the references to it (so it can be garbage collected) > and then read back in (perhaps in pieces) as needed. This could be fairly > cleanly expressed monadically. So does anyone know if someone has created > something like this? Yes. I had faced essentially the same problem. It is indeed tricky to prevent memoization: GHC is very good at it. The following article explains the solution: ``Preventing memoization in (AI) search problems'' http://okmij.org/ftp/Haskell/index.html#memo-off

1 0

[Q] multiparam class undecidable types - how to get this example to typecheck?
by Matthias Fischmann 09 May '12

09 May '12

Hi everybody, I am torturing the ghc type inference extensions, and I think i managed to break something, either in ghc or (more likely) in my brain: | {-# language FlexibleInstances, MultiParamTypeClasses, UndecidableInstances #-} | | module Main | where | | class Table table cell where | toLists :: table -> [[cell]] | fromLists :: [[cell]] -> table | | instance Table [[cell]] cell where | toLists = id | fromLists = id | | -- why i am using a class (not relevant for my question) - | -- data FastTable a = FastTable ... | -- instance Table (FastTable a) a where ... | | instance (Table a c, Show c) => Show a where | showsPrec p t = showParen (p > 10) $ showString "fromLists " . shows (toLists t) ghc 7.0.3 sais: | Overlapping instances for Show [[cell0]] | arising from a use of `shows' | Matching instances: | instance Show a => Show [a] -- Defined in GHC.Show | instance (Table a c, Show c) => Show a | -- Defined at /home/mf/tmp/z.hs:18:10-38 | In the second argument of `(.)', namely `shows (toLists t)' I would have thought that there is on overlap: the instance in my code above defines how to show a table if the cell is showable; the (allegedly) overlapping instance defines how to show lists of alpha if alpha is showable. So I was expecting the reduction to go something like: . table ~> [[cell]] (via whichever instance of class Table applies) . [[cell]] ~> [cell] (via instance "Show a => Show [a]") . [cell] ~> cell (via instance "Show a => Show [a]") But it gets worse. I decided to ignore the problem for now and be happy with at least showing the first cell in the upper left corner of the table: | instance (Table a c, Show c) => Show a where | showsPrec p t = showParen (p > 10) $ showString "fromLists " . shows (head . head $ toLists t) to that, ghc 7.0.3 sais: | /home/mf/tmp/z.hs:19:66: | Context reduction stack overflow; size = 21 | Use -fcontext-stack=N to increase stack size to N | $dShow :: Show c19 | $dShow :: Show c18 | [...] shouldn't type inference be able to determine that | ((head . head $ toLists t) :: c and use the instance guaranteed by the instance declaration's class constraint (Show c)? I suspect that there should be a type annotation that would make this approach possible, but even then I am curious what this behavior means. Should I upgrade to a more grown-up release of ghc? Any hints or pointers appreciated. (: Thanks, Cheers, Matthias

1 0

LLVM M.D. source code?
by Greg Fitzgerald 09 May '12

09 May '12

A paper, LLVM M.D.: A Denotational Translation Validator, mentions the source code for LLVM M.D is available here: http://llvm-md.seas.harvard.edu/ I can't seem to spot it there or on Hackage. Anyone seen it? Thanks, Greg

1 0

Unit and pair
by MigMit 09 May '12

09 May '12

Hi café, a quick question. Is there a somewhat standard class like this: class Something c where unit :: c () () pair :: c x y -> c u v -> c (x, u) (y, v) ? I'm using it heavily in my current project, but I don't want to repeat somebody else's work, and it seems general enough to be defined somewhere; but my quick search on Hackage didn't reveal anything. I know about arrows; this, however, is something more general, and it's instances aren't always arrows.

4 6

bytestring, array and Safe Haskell
by Francesco Mazzoli 08 May '12

08 May '12

Why are http://hackage.haskell.org/packages/archive/bytestring/0.9.2.1/doc/html/Dat… and http://hackage.haskell.org/packages/archive/array/0.4.0.0/doc/html/Data-Arr… Safe-inferred? The first one uses inlinePerformIO, so it clearly shouldn't be marked as Safe. Maybe Safe Haskell doesn't check that function? The second is a bit messier since it uses unboxed types and primitive operations... But they clearly should be marked as Unsafe, and it surprises me that Safe Haskell is that relaxed when checking for safe functions. Francesco.

2 2

Can Haskell outperform C++?
by Isaac Gouy 08 May '12

08 May '12

2012/5/8 Silvio Frischknecht >Also I challenge anyone to improve one of the haskell programs there. >It'd be cool if we could make haskell get a higher rank. I recently >managed to improve the Fasta algorithm, but not by much. Also I think >the benchmarks don't use llvm flag. It says somewhere that they don't >measure llvm because they don't have time. But I think they are >refering to clang. So maybe someone should tell them to turn on the >llvm flag since it makes a lot of haskell programs faster. Several GHC versions have come and gone since the Haskell benchmarks game programs were written, so perhaps it is time that a dozen new programs were written to replace those old programs - new programs that take advantage of GHC 7.4.1 and -llvm.

1 0

ANN: hspec-1.1.0
by Simon Hengel 07 May '12

07 May '12

Hi, I'm glad to announce a new release of hspec[1]. Detailed release notes are at [2]. Introductory documentation is at [3]. Cheers, Simon [1] http://hackage.haskell.org/package/hspec-1.1.0 [2] https://github.com/hspec/hspec/blob/master/CHANGES.markdown [3] http://hspec.github.com/

1 0

correction
by Serge D. Mechveliani 07 May '12

07 May '12

Correction to my last letter: Run on the second terminal > ./iface --> Run on the second terminal > ./a.out ------ Sergei mechvel(a)botik.ru

1 0

Haskell-Type-Exts -- Typechecker as a Library
by Shayan Najd Javadipour 07 May '12

07 May '12

Hello Haskell Cafe! Recently, I got my proposal “Haskell-Type-Exts”--submitted to haskell community--accepted for Google SoC 2012! I have the luxury (thanks to Haskell.org GSoC committee) to develop a typechecker[1] for ASTs extracted by HSE[2] during this summer. HSE is one of the most widely used (if not the most popular) standalone parsers for Haskell 2010 plus a wide variety of extensions. HSE is written (and maintained) by Niklas Broberg and he is also mentoring this project. To be realistic, it is a rather challenging project and support of the community is vitally important to achieve the goals. I have a weblog accessible at http://cleantypecheck.wordpress.com/ dedicated to this topic. I plan to use it as the main media to communicate with people interested. Also, you can contact me directly through [shayan at chalmers d0t se]. If you see yourself as a potential user of the tool or by any reason you are interested , I'd highly appreciate if you would take a look at the following post and leave your comment/suggestions: http://cleantypecheck.wordpress.com/2012/05/03/inquiry/ Thanks! /Shayan [1] http://hackage.haskell.org/package/haskell-type-exts [2] http://hackage.haskell.org/package/haskell-src-exts

1 0