- Haskell-Cafe - Haskell.org

Types and Trees
by Matt Morrow 03 Sep '08

03 Sep '08

I really learned a lot from writing the below code, and thought I'd share it with the group. I'm slightly at a loss for words, having just spent the last two hours on this when I most certainly should have been doing other work, but these are two hours I won't regret. I'm very interested in hearing others' thoughts on "this", where "this" is "whatever comes to mind". Regards, Matt {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} module TT where import Data.Tree import Data.Typeable (Typeable(..),TypeRep(..),TyCon(..) ,typeRepTyCon,typeRepArgs,tyConString) import Language.Haskell.TH(Type(..),mkName) -------------------------------------------------------- class ToType a where toType :: a -> Type class ToTree a b where toTree :: a -> Tree b {- Typeable a | typeOf | (0) | v toType TypeRep - - - - - - - - > Type | (4) | toTree | (1) (2) | toTree | | v (3) v Tree TyCon ---------------> Tree Type toTree -} -- (0) typeableToTypeRep :: (Typeable a) => a -> TypeRep typeableToTypeRep = typeOf -- (1) instance ToTree TypeRep TyCon where toTree ty = Node (typeRepTyCon ty) (fmap toTree . typeRepArgs $ ty) -- (2) instance ToTree Type Type where toTree (AppT t1 t2) = let (Node x xs) = toTree t1 in Node x (xs ++ [toTree t2]) toTree t = Node t [] -- (3.a) instance ToType TyCon where toType tyC = let tyS = tyConString tyC in case tyS of "->" -> ArrowT "[]" -> ListT "()" -> TupleT 0 ('(':',':rest) -> let n = length (takeWhile (==',') rest) in TupleT (n+2) _ -> ConT . mkName $ tyS -- (3.b) instance ToType (Tree TyCon) where toType (Node x xs) = foldl AppT (toType x) (fmap toType xs) -- (3) instance ToTree (Tree TyCon) Type where toTree = toTree . toType -- (4) instance ToType TypeRep where toType = toType . (toTree::TypeRep->Tree TyCon) -- (0) typeOf -- (1) toTree -- (2) toTree -- (3) toTree -- (4) toType -- (0) -> (1) tyConTree :: (Typeable a) => a -> Tree TyCon tyConTree = toTree . typeOf -- (0) -> (1) -> (3) typeTree_a :: (Typeable a) => a -> Tree Type typeTree_a = (toTree::Tree TyCon->Tree Type) . (toTree::TypeRep->Tree TyCon) . typeOf -- (0) -> (4) -> (2) typeTree_b :: (Typeable a) => a -> Tree Type typeTree_b = (toTree::Type->Tree Type) . (toType::TypeRep->Type) . typeOf diagram_commutes :: (Typeable a) => a -> Bool diagram_commutes a = typeTree_a a == typeTree_b a -- ghci> diagram_commutes x0 -- True x0 :: (Num a) => ((a,(a,((a,a),a))),(a,(a,a))) x0 = ((0,(0,((0,0),0))),(0,(0,0))) -------------------------------------------------------- printTree :: (Show a) => Tree a -> IO () printTree = putStr . drawTree . fmap show printForest :: (Show a) => Forest a -> IO () printForest = putStr . drawForest . (fmap . fmap) show -------------------------------------------------------- {- ghci> printTree $ tyConTree x0 (,) | +- (,) | | | +- Integer | | | `- (,) | | | +- Integer | | | `- (,) | | | +- (,) | | | | | +- Integer | | | | | `- Integer | | | `- Integer | `- (,) | +- Integer | `- (,) | +- Integer | `- Integer ghci> printTree $ typeTree_a x0 TupleT 2 | +- TupleT 2 | | | +- ConT Integer | | | `- TupleT 2 | | | +- ConT Integer | | | `- TupleT 2 | | | +- TupleT 2 | | | | | +- ConT Integer | | | | | `- ConT Integer | | | `- ConT Integer | `- TupleT 2 | +- ConT Integer | `- TupleT 2 | +- ConT Integer | `- ConT Integer ghci> printTree $ typeTree_b x0 TupleT 2 | +- TupleT 2 | | | +- ConT Integer | | | `- TupleT 2 | | | +- ConT Integer | | | `- TupleT 2 | | | +- TupleT 2 | | | | | +- ConT Integer | | | | | `- ConT Integer | | | `- ConT Integer | `- TupleT 2 | +- ConT Integer | `- TupleT 2 | +- ConT Integer | `- ConT Integer -} --------------------------------------------------------

1 0

What monad am I in?
by Henry Laxen 03 Sep '08

03 Sep '08

Dear Group, When I fire up ghci and define: increment x = return (x+1) I can say: Main> increment 1 and ghci dutifully replies 2. Also as expected, the type signature of increment is: (Num a, Monad m) => a -> m a However, if I say: Main> let a = increment 1 I get: <interactive>:1:8: Ambiguous type variable `m' in the constraint: `Monad m' arising from a use of `increment' at <interactive>:1:8-18 Probable fix: add a type signature that fixes these type variable(s) Have I, like Monsier Jourdain, been running in the IO monad all my life, and didn't even know it? Thanks, Henry Laxen

6 5

ANN: zip-archive 0.0
by John MacFarlane 03 Sep '08

03 Sep '08

I've written a library, zip-archive, for dealing with zip archives. Haddock documentation (with links to source code): http://johnmacfarlane.net/zip-archive/ Darcs repository: http://johnmacfarlane.net/repos/zip-archive/ It comes with an example program that duplicates some of the functionality of 'zip' (configure with '-fexecutable' to build it). I intend to put it on HackageDB, but I thought I'd get some feedback first. Bug reports, patches, and suggestions on the API are all welcome. John

3 3

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

ICFP09 Announcement
by Matthew Fluet (ICFP Publicity Chair) 02 Sep '08

02 Sep '08

+--------------------------------------------------------------------+ ANNOUNCEMENT The 14th ACM SIGPLAN International Conference on Functional Programming ICFP 2009 31st August - 2nd September 2009 Edinburgh, United Kingdom ICFP provides a forum for researchers and developers to hear about the latest work on the design, implementations, principles, and uses of functional programming. ICFP 2009 will be held in Scotland's historic capital city of Edinburgh, during the final week of the Edinburgh International Festival. Further information is available from: http://www.cs.nott.ac.uk/~gmh/icfp09.html Graham Hutton General Chair, ICFP 2009 +--------------------------------------------------------------------+ | Dr Graham Hutton Email : gmh(a)cs.nott.ac.uk | | Functional Programming Lab | | School of Computer Science Web : www.cs.nott.ac.uk/~gmh | | University of Nottingham | | Jubilee Campus, Wollaton Road Phone : +44 (0)115 951 4220 | | Nottingham NG8 1BB, UK | +--------------------------------------------------------------------+

1 0

REMINDER: OpenSPARC project application deadline this Friday
by Duncan Coutts 02 Sep '08

02 Sep '08

http://haskell.org/opensparc/ The deadline for applications for the Haskell OpenSPARC project is rapidly approaching. Applications have to be sent to: opensparc(a)community.haskell.org by the end of this week, Friday the 5th September. If you want any comments on your application before you submit it then contact me directly. Duncan (project coordinator) In other news, the server that Sun Microsystems donated to the community has just gone online at Chalmers: http://blog.well-typed.com/2008/09/the-new-haskellorg-community-sparc-serve…

1 0

Re: [Haskell] The initial view on typed sprintf and sscanf
by Matthew Brecknell 02 Sep '08

02 Sep '08

oleg [1]: > We demonstrate typed sprintf and typed sscanf sharing the same > formatting specification. [1]http://www.haskell.org/pipermail/haskell/2008-August/020605.html Reading Oleg's post, I noticed that it is quite straightforward to generalise printing to arbitrary output types. > class Monoid p => Printf p where > printChar :: Char -> p > --etc > > intp :: Printf p => F a b -> (p -> a) -> b > intp FChr k = \c -> k (printChar c) > intp (a :^ b) k = intp a (\sa -> intp b (\sb -> k (mappend sa sb))) > --etc > > printf :: Printf p => F p b -> b > printf fmt = intp fmt id The Printf instances for String, ShowS, ByteStrings, and IO () are all trivial. Printing directly to a file (without building an intermediate string) is slightly more interesting: > instance Monad m => Monoid (ReaderT r m ()) where > mempty = return () > mappend = (>>) > > instance Printf (ReaderT Handle IO ()) where > printChar c = ask >>= \h -> liftIO (hPutChar h c) > --etc > > (<<) :: Handle -> ReaderT Handle IO () -> IO () > (<<) = flip runReaderT > > test_fprintf h = h << printf (lit "Hello " ^ lit "World" ^ chr) '!' Unfortunately, I don't seem to be able to make the expected fprintf function, because printf's format-dependent parameter list makes it impossible to find a place to pass the handle. Hence the C++-like (<<) ugliness.

5 5

Fast parallel binary-trees for the shootout: Control.Parallel.Strategies FTW!
by Don Stewart 01 Sep '08

01 Sep '08

The Computer Language Benchmarks Game recently got a quad core 64 bit machine. Initial results just porting the single-threaded Haskell benchmarks to 64 bit look rather pleasing, http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=all Note that C++, D, Clean et al aren't ported to the 64 bit machine yet (and perhaps some implementations won't survive the 64 bit switch). Now, none of the Haskell programs are annotated for parallelism yet, despite that quad core sitting there ready to go. I've a conjecture that fast, smp capable, concise code, of the kind GHC produces, could dominate the shootout for a while to come, if we can effectively utilise those cores. This is a chance to make an impression! So, the first parallel benchmark has been submitted by Tom Davies and me, a parallel implementation of the binary-trees benchmark, using the Control.Parallel.Strategies lib to set up some top level parallel tasks. Initial results look promising, with the old entry: * Single core, no heap hints: 26.9s $ ghc -O2 -fasm Original.hs --make $ time ./Original 20 ./Original 20 26.79s user 0.16s system 100% cpu 26.933 total Looking at the GC stats (-sstderr) we see its spending too much time doing GC, 57.8%, so we can improve that by setting a default heap size: * Single core, with heap hints: 13.7s $ time ./Original 20 -A350M ... ./Original 20 +RTS -A350M 13.54s user 0.27s system 100% cpu 13.791 total Halves runtime in comparison to the current entry, and reduces GC to 3.8%. * Now, the parallel version, changing one line to use a parMap strategy, and using the N+1 capabilities rule, $ ghc -O2 -fasm Parallel2.hs --make -threaded $ time ./Parallel2 20 +RTS -N5 -A350M ... ./Parallel2 20 +RTS -N5 -A350M 15.38s user 1.57s system 305% cpu 5.684 total So 305% productive (not too bad for this memory-heavy program), and a good speedup. Observations: * check GC stats with -sstderr, then use -AxxxM to set a default heap size * parallelise the top level control using speculative strategies * Use -N+1 capabilities. -- Don

1 1

getting Quickcheck 2.0
by Wolfgang Jeltsch 01 Sep '08

01 Sep '08

Hello, is there a reason why Quickcheck 2.0 isn’t released via Hackage? Does anybody know where to get it? The darcs repository already has 2.1 as the version number in the Cabal file but Hackage still only has 1.1.0.0. Best wishes, Wolfgang

2 1

Haskell Propeganda
by Niels Aan de Brugh 01 Sep '08

01 Sep '08

On Sun, Aug 24, 2008 at 5:44 AM, Thomas M. DuBuisson < thomas.dubuisson(a)gmail.com> wrote: > wrt head [], Niels said: > > So now what? Action plan = [] > > Oh come now. Between ghci, hpc, and manual analysis I've never hit a > Haskell error and thrown my hands up, "I can't go any further, I'm at a > complete loss!" Also it helps that I run into this extremely rarely - I > have a larger habit of hidding black holes :-( I've never used Haskell in an engineering environment, but I have encountered problems that would've been easier to analyze with a step function (almost without exception in a stateful computation, e.g. functions using recursion or some state monad). For example, a graphical frond-end to the GHCi debugger would've been really helpful, especially for new users. C/C++ programmers on Linux have gdb but I know nobody that uses the tool directly on the bare command line. Niels said: > > Thank you for the URL, but I'm aware of the work in GHC(i). > > It might interest you to know some people actually use hpc for debugging > with reasonble success - it colors the unevaluated sections and this can > be very helpful in determining where a program stopped and threw an > exception. I haven't used HPC myself (I use -fwarn-incomplete-patterns but that's about it for "coverage" analysis) but it looks like a powerful tool. Statement and branch coverage are very imporant metrics e.g. to measure test coverage. However, I feel that using a profiler to do a debuggers job is really a poor man's solution. Just like the trace function (tracing/logging itself is useful, but not as a debugger tool). > If you have your eyes on the future you should see Dana Xu's work on > static contract checking (check out her Cambridge page). Thanks for the suggestion, I'll be sure to check that out. I use design by contract on a daily basis, but in a language like C++ it's never more than a couple of glorified asserts. My opinion is that if you want to do contracts good (i.e. not with some macro kludge) it needs to be embedded into the language. I've been looking at Spec#, that looks like a very powerful extension to C#. I think contracts could fit even better in a pure functional language. Checking contracts statically would be awesome, but doing dynamic DbC well is already harder than it seems (e.g. in concurrent code that uses locks). Regards, Niels

1 0