June 2007 - Haskell-Cafe

Re: [Haskell-cafe] Memo + IORef
by David House 16 Jun '07

16 Jun '07

Tony Morris writes: > Yes, but where does the IORef live? Wouldn't I have to pass it back and > forth between invocations? If not, where do I get the IORef from on > subsequent invocations? Got a short example? That's where the unsafePerformIO comes in. With unsafePerformIO and IORefs, you can have global mutable variables: {-# NOINLINE #-} memo :: IORef Int memo = unsafePerformIO (newIORef Nothing) f = unsafePerformIO $ do ref <- readIORef memo case ref of Just val -> return val Nothing -> let val = complexCalculation in writeIORef memo val >> return val Something like that. If f took an argument then you'd probably use a IORef Map or IORef IntMap or something in place of IORef Int. Be careful to: 1) Not break referential transparency. I.e. in my example, f will always return the same value, how ever many times you call it. It's possible to break this property using this trick. 2) Not use polymorphic references, as they lead to type unsafety [1]. 3) Always use the {-# NOINLINE #-} pragma on any IORefs you create this way. [1]: http://haskell.org/ghc/docs/latest/html/libraries/base/System-IO-Unsafe.htm… -- -David House, dmhouse(a)gmail.com

1 0

Memo + IORef
by Tony Morris 16 Jun '07

16 Jun '07

I was told on #haskell (IRC) the other day that it is possible to write a general memoisation table using IORef and unsafePerformIO. I can't think of how this can be achieved without writing to a file, since a function cannot hold state between invocations. What am I missing? -- Tony Morris http://tmorris.net/

2 1

Template haskell problem
by Marc Weber 16 Jun '07

16 Jun '07

I want to write a a template haskell function deriving show for data types without constructor. -- example -- data A a -- the derived instance: -- instance (Show a) => Show (A a) where -- show _ = "A " ++ show (undefined :: a) deriveShowNoConstructors :: Name -> Q [ Dec ] deriveShowNoConstructors name = do TyConI (DataD [] _ typeParams [] []) <- reify name runIO $ putStrLn $ show typeParams runIO $ hFlush stdout return [ InstanceD (contexts typeParams) (AppT (ConT nShow) (iOf (ConT name) typeParams)) [ FunD (mkName "show") [Clause [WildP] (NormalB (foldr (\a n -> InfixE (Just a) (VarE (mkName "++")) (Just n)) (LitE (StringL (pprint name))) (map und typeParams))) -- <<< replacing occurs here (see below) [] ] ] ] where contexts = map (\n -> AppT (ConT nShow) (VarT n) ) -- ( ... ) => iOf = foldr (\n a -> AppT a (VarT n) ) -- ( ... ) where nShow = mkName "Show" und n = AppE (VarE (mkName "show")) (SigE (VarE (mkName "undefined")) (ForallT [n] [] (VarT n))) -- undefined :: typePara But when trying to run it with: data A a b c [ .. module change ] $( do l <- deriveShowNoConstructors ''A runIO $ putStrLn $ pprint l runIO $ hFlush stdout return l ) I get the error: src-HListMissing/HListMissingTest.hs|29| 3: || Ambiguous type variable `a[ad8]' in the constraint: || `Show a[ad8]' || arising from use of `show' || at src-HListMissing/HListMissingTest.hs:(29,3)-(32,13) || Probable fix: add a type signature that fixes these type variable(s) || src-HListMissing/HListMissingTest.hs|29| 3: || Ambiguous type variable `b[ada]' in the constraint: || `Show b[ada]' || arising from use of `show' || at src-HListMissing/HListMissingTest.hs:(29,3)-(32,13) || Probable fix: add a type signature that fixes these type variable(s) || src-HListMissing/HListMissingTest.hs|29| 3: || Ambiguous type variable `c[adc]' in the constraint: || `Show c[adc]' || arising from use of `show' || at src-HListMissing/HListMissingTest.hs:(29,3)-(32,13) || Probable fix: add a type signature that fixes these type variable(s) When replacing typeParams with [] (thus only show _ = "Class" instead of show _ = "Class" ++ (undefined:: a) ++ ... it compiles and prints the pretty printed abstract syntax tree as expected: || instance (Show a_0, Show b_1, Show c_2) => Show (THStuff.A c_2 || b_1 || a_0) || where show _ = "THStuff.A" Do you see what I am doing wrong? The function und :: Name -> Exp und n = AppE (VarE (mkName "show")) (SigE (VarE (mkName "undefined")) (ForallT [n] [] (VarT n))) should create the (show $ undefined :: a) part. Marc Weber

1 1

lists with mixed types
by oleg＠pobox.com 16 Jun '07

16 Jun '07

Anatoly Yakovenko wrote: > but what i really want to do is just do > map func [1, 2.0] > [1, "2.0"] > > I understand that this is impossible in haskell, If you use a heterogeneous list, it is possible. The HList paper describes such examples. http://homepages.cwi.nl/~ralf/HList/ > but why cant the > compiler generate the Foo and Bar data types for me and just require > that i have a func defined for Int -> Int and Float -> String? It can. One can write something like lst = (1::Int) `eCons` True `eCons` 'a' `eCons` eNil the result is a true Haskell list of the type [Either Int (Either Bool Char)] and the contents [Left 1, Right (Left True), Right (Right 'a')] Haskell figures out the union (Either) type automatically. Using a function like hOccurs one can `downcast' from that union type to a specific type (Int or Char) so one does not need to care about the number and amount of Left and Right... In more detail, this is described in Section 5.5 of http://homepages.cwi.nl/~ralf/OOHaskell and code at http://darcs.haskell.org/OOHaskell/ShapesEither.hs

1 0

Re: [Haskell-cafe] Sneaking haskell in the workplace -- cleaning csv files
by Donn Cave 16 Jun '07

16 Jun '07

Quoth Tomasz Zielonka <tomasz.zielonka(a)gmail.com>: | On Fri, Jun 15, 2007 at 11:31:36PM +0100, Jim Burton wrote: | > I think that would only work if there was one column per line...I didn't | > make it clear that as well as being comma separated, the delimiter is | > around each column, of which there are several on a line so if the | > delimiter is ~ a file might look like: | > | > ~sdlkfj~, ~dsdkjf~ #eo row1 | > ~sdf | > dfkj~, ~dfsd~ #eo row 2 | | It would be easier to experiment if you could provide us with an | example input file. If you are worried about revealing sensitive | information, you can change all characters other then newline, | ~ and , to "A"s, for example. An accompanying output file, for checking | correctness, would be even nicer. Yes, especially if there's anyone else as little acquainted with CSV files as I am! I have never bothered to learn to work with multiple lines in sed, but from what I gather so far, the following awk would do it -- awk '{ if (/~$/) print; else printf "%s", $0 }' (literal separator for legibility.) I know we're not exactly looking for an awk or sed solution here, but thought it might add some context to the exercise anyway. Donn Cave, donn(a)drizzle.com

1 0

This is an interesting place to showcase Haskell.
by Michael T. Richter 16 Jun '07

16 Jun '07

http://en.literateprograms.org/LiteratePrograms:Welcome There's some Haskell there already, but I think a lot more could be shown there. Even code dumps of things would be nice. They can always be explained later. -- Michael T. Richter <ttmrichter(a)gmail.com> (GoogleTalk: ttmrichter(a)gmail.com) Never, ever, ever let systems-level engineers do human interaction design unless they have displayed a proven secondary talent in that area. Their opinion of what represents good human-computer interaction tends to be a bit off-track. (Bruce Tognazzini)

2 4

GHCI hangs on Gtk2HS SOE on Windows, but GHC works fine?
by bf3＠telenet.be 15 Jun '07

15 Jun '07

I'm learning Haskell using Paul Hudak's book SOE. I'm using GHC 6.6 under Windows XP. GHC on Windows does not seem to come with HGL (is this correct?), so I used Gtk2HS, which contains a SOE implementation. I noticed that most programs hang when using GHCI, but they work fine with GHC. For example, the following mini program: import Graphics.SOE.Gtk main = runGraphics (openWindow "Stuck" (300,300) >>= closeWindow) completely hangs GHCI when running 'main', but using the GHC-created executable, a window correctly pops up and closes immediately, nicely returning to the command prompt. As GHCI is easier for experimenting, it would be nice if this worked. Thanks, Peter

2 1

Construct all possible trees
by Andrew Coppin 15 Jun '07

15 Jun '07

Well, I eventually came up with this: --------------------------------- data Tree = Leaf Int | Branch Tree Tree deriving Show pick :: [x] -> [(x,[x])] pick = pick_from [] pick_from :: [x] -> [x] -> [(x,[x])] pick_from ks [] = [] pick_from ks xs = (head xs, ks ++ tail xs) : pick_from (ks ++ [head xs]) (tail xs) trees :: [Int] -> [Tree] trees = map fst . (\ts -> all_trees 1 (2 * length ts) ts) . map Leaf all_trees :: Int -> Int -> [Tree] -> [(Tree,[Tree])] all_trees n m ts | n > m = [] | otherwise = pick ts ++ sub_trees n m ts sub_trees :: Int -> Int -> [Tree] -> [(Tree,[Tree])] sub_trees n m ts = do let n2 = n * 2 (t0,ts0) <- all_trees n2 m ts (t1,ts1) <- all_trees n2 m ts0 return (Branch t0 t1, ts1) ----------------------------- For example, trees [1,2,3] now gives Leaf 1 Leaf 2 Leaf 3 Branch (Leaf 1) (Leaf 2) Branch (Leaf 1) (Leaf 3) Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)) Branch (Leaf 1) (Branch (Leaf 3) (Leaf 2)) Branch (Leaf 2) (Leaf 1) Branch (Leaf 2) (Leaf 3) Branch (Leaf 2) (Branch (Leaf 1) (Leaf 3)) Branch (Leaf 2) (Branch (Leaf 3) (Leaf 1)) Branch (Leaf 3) (Leaf 1) Branch (Leaf 3) (Leaf 2) Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2)) Branch (Leaf 3) (Branch (Leaf 2) (Leaf 1)) Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3) Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 2) Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 3) Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 1) Branch (Branch (Leaf 3) (Leaf 1)) (Leaf 2) Branch (Branch (Leaf 3) (Leaf 2)) (Leaf 1) which looks pretty comprehensive to me! The derivation wasn't easy. It goes something like this: First, the "pick" function takes a list and picks a single element from it, returning the element picked and the remaining unpicked elements. It does this inside the list monad, thus representing every possibel choice. (It's defined in terms of pick_from, which isn't used anywhere else. The algorithm should be fairly self-evident.) Next, we have "trees" which transforms a list of integers into a list of trivial 1-leaf trees to be processed by "all_trees". The "all_trees" function calls pick to select all possible trivial trees, and then calls "sub_trees" to pick all possible nontrivial trees. The code for sub_trees would go something like this: sub_trees ts = do t0 <- ts t1 <- ts return (Branch t0 t1) But now t0 == t1 sometimes, which we cannot allow. Hence the "pick" function: sub_trees ts = do (t0,ts0) <- pick ts (t1,ts1) <- pick ts0 return (Branch t0 t1, ts1) And now the problem is solved. However, this only generates all possible 2-leaf trees. To make *all* possible trees, we must be recursive: sub_trees ts = do (t0,ts0) <- all_trees ts (t1,ts1) <- all_trees ts0 return (Branch t0 t1, ts1) And now it works properly. Er... wait. Now we have an infinite recursive loop! all_trees --> sub_trees --> all_trees (with the same arguments)! The only way I could figure out to avoid that is to count how big the input list is - and hence how deep the tree can possibly be. Then you keep track of how deep you are, and abort when you get too deep. I added lots of hackery to avoid recomputing stuff. Makes the code look very messy and ugly...

1 2

ICFP07 Accepted Papers
by Matthew Fluet (ICFP Publicity Chair) 15 Jun '07

15 Jun '07

Accepted Papers ICFP 2007: International Conference on Functional Programming http://www.informatik.uni-bonn.de/~ralf/icfp07.html Freiburg, Germany, 1-3 October 2007 The ICFP 2007 Program Chair and Committee are pleased to announce that the following papers have been accepted for the conference. Additional information regarding the final program, invited speakers, and registration will be forthcoming. However, the Local Arrangements Chair offers the following advice regarding hotel reservations: * As September and October is Freiburg's main tourist season, it is important that participants book hotel rooms early. The blocks of hotel rooms reserved for ICFP participants will be held until August 1. It is expected that many downtown hotels will be fully booked at the time of the conference. [However, there should be little to no penalty for cancelling a hotel room reservation after August 1.] More details regarding accommodation and travel may be obtained from the ICFP 2007 Local Information webpage: http://proglang.informatik.uni-freiburg.de/ICFP2007/ Accepted papers ~~~~~~~~~~~~~~~ A Generic Usage Analysis with Subeffect Qualifiers by Jurriaan Hage, Stefan Holdermans, Arie Middelkoop Experience Report: A Haskell interpreter for CellML by Jonathan Cooper, Steve McKeever A type directed translation of MLF to System-F by Daan Leijen A Type System for Recursive Modules by Derek Dreyer Adding Delimited and Composable Control to a Production Programming Environment by Matthew Flatt, Gang Yu, Robert Bruce Findler, Matthias Felleisen Bidirectionalization Transformation based on Automatic Derivation of View Complement Functions by Kazutaka Matsuda, Zhenjiang Hu, Keisuke Nakano, Makoto Hamana, Masato Takeichi Experience Report: Building an Eclipse-based IDE for Haskell by Leif Frenzel Compiling with Continuations, Continued by Andrew J. Kennedy Constructor specialisation for Haskell programs by Simon Peyton Jones Evaluating High-Level Distributed Language Constructs by Jan Nystrom, Phil Trinder, David King Extensible Pattern Matching via a Lightweight Language Extension by Don Syme, Gregory Neverov, James Margetson Faster laziness using dynamic pointer tagging by Simon Marlow, Alexey Rodriguez, Simon Peyton Jones Feedback Directed Implicit Parallelism by Tim Harris, Satnam Singh Finger Trees in Russell by Matthieu Sozeau Functional Pearl: The Great Escape by David Herman Experience Report: Functional Programming in C-Rules by Jeremy Wazny Inductive Reasoning about Effectful Data Types by Andrzej Filinski, Kristian Stoevring iTasks: Executable Specifications of Interactive Work Flow Systems for the Web by Rinus Plasmeijer, Peter Achten, Pieter Koopman Lazy Call-By-Value Evaluation by Frank Huch, Bernd Brassel, Sebastian Fischer, Michael Hanus, German Vidal McErlang: A Model Checker for a Distributed Functional Programming Language by Lars-Åke Fredlund, Hans Svensson On Barron and Strachey's Cartesian Product Function by Michael Spivey, Olivier Danvy Ott: Effective Tool Support for the Working Semanticist by Peter Sewell, Francesco Zappa Nardelli, Scott Owens, Gilles Peskine, Thomas Ridge, Susmit Sarkar, Rok Strnisa Relating Complexity and Precision in Control Flow Analysis by David Van Horn, Harry Mairson Experience Report: Scheme in Commercial Web Application Development by Noel Welsh, David Gurnell Stream Fusion: From Lists to Streams to Nothing at All by Duncan Coutts, Roman Leshchinskiy, Don Stewart Tangible Functional Programming by Conal Elliott Termination Analysis and Call Graph Construction for Higher-Order Functional Programs by Damien Sereni The Portable R6RS Syntax System by Abdulaziz Ghuloum, R. Kent Dybvig Experience Report: The Reactis Validation Tool by Steve Sims, Daniel C. DuVarney Type-safe Higher-order Channels in ML-like Languages by Sungwoo Park User-Friendly Functional Programming for Web Mashups by Rob Ennals, David Gay Experience Report: Using Functional Programming to Manage a Linux Distribution by Clifford Beshers, David Fox, Jeremy Shaw

1 0

Re: [Haskell-cafe] Optimising UTF8-CString -> String marshaling, plus comments on withCStringLen/peekCStringLen
by Alistair Bayley 15 Jun '07

15 Jun '07

> > {- Arity: 4 Strictness: LSSL -} > > Right. Unboxed args are always given the annotation L. So that function > is strict in that pointer arg, but GHC is choosing not to unbox it. I'm > not sure why that's the case. I thought maybe it was because I hadn't said -funbox-strict-fields, but it didn't change when I did. > > Is there some semantic advantage to bang-patterns, or is it just a > > syntactic convenience? > > It's syntactic convenience. I've noticed differences between strictness guards and bang-patterns with GHC. This is a problem, I think, because bang-patterns are GHC only, and I wanted to keep the code portable. This strictness guard: readUTF8Char :: Int -> Int -> Ptr Word8 -> IO Char readUTF8Char x offset p | () !x !offset !p !False = undefined | otherwise = ... where x ! y = seq x y results in this simplifier output: [Arity 3 Str: DmdType LSS] $wreadUTF8Char_r38I = \ (ww_s30B :: GHC.Prim.Int#) (w_s30D :: GHC.Base.Int) (w1_s30E :: GHC.Ptr.Ptr GHC.Word.Word8) -> However, if I change this to: {-# OPTIONS_GHC -fbang-patterns #-} ... readUTF8Char :: Int -> Int -> Ptr Word8 -> IO Char readUTF8Char !x !offset !p | otherwise = then I get this simpifier output: [Arity 3 Str: DmdType LLL] $wreadUTF8Char_r38n = \ (ww_s2Zk :: GHC.Prim.Int#) (ww1_s2Zo :: GHC.Prim.Int#) (ww2_s2Zs :: GHC.Prim.Addr#) -> Also, with bang-patterns I've noticed that fromUTF8Ptr transforms into two functions, which contain very similar code: [Arity 5] Foreign.C.UTF8.$s$wfromUTF8Ptr = \ (acc_X151 :: GHC.Base.String) (new_s_a2GQ :: GHC.Prim.State# GHC.Prim.RealWorld) (a87_a2GR :: GHC.Base.Char) (ww_s2ZH :: GHC.Prim.Addr#) (sc_s36j :: GHC.Prim.Int#) -> [Arity 4 Str: DmdType LLSL] Foreign.C.UTF8.$wfromUTF8Ptr = \ (ww_s2ZD :: GHC.Prim.Int#) (ww1_s2ZH :: GHC.Prim.Addr#) (w_s2ZJ :: GHC.Base.String) (w1_s2ZK :: GHC.Prim.State# GHC.Prim.RealWorld) -> $wfromUTF8Ptr calls itself and $s$wfromUTF8Ptr, but $s$wfromUTF8Ptr only every calls itself, so $wfromUTF8Ptr could be considered the wrapper, and $s$wfromUTF8Ptr the worker, I guess. AFAICT it's a transformation of the various cases in fromUTF8Ptr: | x <= 0x7F -> fromUTF8Ptr (bytes-1) p (chr x:acc) | x <= 0xBF && bytes == 0 -> error "fromUTF8Ptr: ..." | x <= 0xBF -> fromUTF8Ptr (bytes-1) p acc | otherwise -> do c <- readUTF8Char x bytes p fromUTF8Ptr (bytes-1) p (c:acc) The first case, x <= 0x7F, results in a call to $s$wfromUTF8Ptr. The third case, x <= 0xBF, results in a call to $wfromUTF8Ptr. The last case, otherwise, results in a call to $s$wfromUTF8Ptr. The calls to $s$wfromUTF8Ptr pass the newly constructed Char and the rest of the String separately, and they are cons'ed in $s$wfromUTF8Ptr. Not sure what benefit this gives... I don't know what transformation causes this, but it was a bit of a surprise. Alistair

2 3