January 2007 - Haskell-Cafe

Pattern matching
by Stefan Aeschbacher 15 Jan '07

15 Jan '07

Hi I sometimes have a function definition similar to this: myFunction x@(Constructor1 _ _ _ _ _ _) = ... myFunction x@(Constructor2 _ _ _ _ _ _ _ _) = ... which in my eyes is not very elegant and easy to type. Is there an easier way to switch on the different constructors of a type (Data.Generics certainly could be used..)? If not, has thought been put in a pattern matching possibility of the form _*. This would allow: myFunction x@(Constructor1 _*) = ... myFunction x@(Constructor2 _*) = ... Also pattern matches of the form: myFunction2 (Constructor1 _* a _*) = ... could be possible as long as the pattern is non-ambiguous (in this case, only one variable with the type of a is present in this constructor). regards Stefan

3 3

Meaning abbreviations stat file GHC
by Ron 13 Jan '07

13 Jan '07

Dear, I made a profile[1] of a test program: Where can I find documentation for the meaning of everything mentioned below? Or alternatively, can anyone explain them? Where can I see the effect of using the -xt option in this profile? Ron [1] /Main +RTS -p -s -xt -hc 1,372,408,024 bytes allocated in the heap 121,255,600 bytes copied during GC (scavenged) 6,584,692 bytes copied during GC (not scavenged) 2,768,896 bytes maximum residency (68 sample(s)) 2649 collections in generation 0 ( 1.11s) 68 collections in generation 1 ( 0.49s) 6 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 5.97s ( 6.63s elapsed) GC time 1.60s ( 1.88s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.19s ( 0.20s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 7.76s ( 8.71s elapsed) %GC time 20.6% (21.5% elapsed) Alloc rate 229,946,873 bytes per MUT second Productivity 76.9% of total user, 68.5% of total elapsed Ron

1 0

Are GADTs expressive? Simple proof-carrying code in Haskell98
by oleg＠pobox.com 13 Jan '07

13 Jan '07

Inspired by the recent post by Jim Apple, we demonstrate a datatype `Terminates' that can hold only an assuredly terminating (strongly normalizable) term in untyped lambda-calculus. Furthermore, the values of the datatype `Terminates' contain all and only those untyped lambda-calculus terms with that property. As in Jim Apple's solution, to create the value `Terminates', the user submits the term in question and the proof of its termination. The proof will be verified -- and if it holds, the Terminates certificate will be created. As in Jim Apple's solution, verification of the submitted proof has to be done at run-time, to make sure the proof is not fake, that is, has no undefined values. Our solution uses neither GADTs nor typeclasses; in fact, it is in Haskell98. Also, the required proof from the user couldn't be simpler. Jim Apple wrote: > To show how expressive GADTs are, the datatype Terminating can hold > any term in the untyped lambda calculus that terminates, and none that > don't. I don't think that an encoding of this is too surprising, but I > thought it might be a good demonstration of the power that GADTs > bring. The shown GADT encoding seems to be of the kind that is convertible to typeclasses in the straightforward way, see for example, http://pobox.com/~oleg/ftp/Haskell/GADT-interpreter.hs Inn this particular example, GADT do not bring any power. Incidentally, the typeclass encoding has an advantage: If the submitted proof is invalid, the error will be reported at compile time. There is not even a possibility of a run-time error. This is because the typeclasses approach does only type-level computations and does not look at values at all (which may as well be undefined). Placing a value into a (rank-1) datatype forces the typechecker to resolve any constraints associated with the value, or report an error if constraints are not satisfiable. However, it seems that the problem at hand admits a far simpler solution -- in Haskell98. The solution is in spirit of lightweight static capabilities. Here it is: > module PCC (Terminates, -- data constructor is not exported > make_terminates, get_term) where > > import YourFavorite.Lambda_calc > > data Terminates = Terminates{get_term::Term} > > make_terminates :: Term -> Integer -> Maybe Terminates > make_terminates term limit = > case reduce_term_nsteps term limit of > Left _ -> Nothing > Right normal_form -> Just (Terminates term) Because the data constructor is not exported, the only way to construct a value `Terminates' from which a term can be extracted is by invoking the function make_terminates. The function accepts a lambda-term, and a proof of its termination. The proof takes the form of the (upper bound of the) number of steps needed to normalize the term. The function make_terminates checks the proof, by trying to reduce the term that many steps. If the normal form is found in the process, the term is normalizable and we create the certificate. Otherwise, we conclude the termination proof does not hold and we return Nothing. This proof checking is clearly decidable. The module PCC constitutes the `trusted kernel' with respect to the Terminates datatype. The function make_terminates must be rigorously verified in order to deserve our trust. But the same should be said for the GADT or any other solution: e.g., one can easily add a new case alternative to the Normal datatype declaring Omega to be in the normal form.

3 2

mapTuple
by Marco Túlio Gontijo e Silva 13 Jan '07

13 Jan '07

Hello, is there a way to defined something as a map to use in tuples? I tried this: mapTuple f (a, b) = (f a, f b) But the type inferred to it is not as generic as I wanted: mapTuple :: (t -> t1) -> (t, t) -> (t1, t1) Then I tried a different, but not much, implementation: mapTuple' f g (a, b) = (f a, g b) mapTuple f = mapTuple' f f But the inferred type was the same. Is there a way to define a function in which I can be able to do something as this? mapTuple show ("string", True) -- malebria Marco Túlio Gontijo e Silva Correio (MSN): malebria(a)riseup.net Jabber (GTalk): malebria(a)jabber.org Telefone: 33346720 Celular: 98116720 Endereço: Rua Paula Cândido, 257/201 Gutierrez 30430-260 Belo Horizonte/MG Brasil

8 11

different performance of equivalent expression
by Alexander Vodomerov 13 Jan '07

13 Jan '07

Hello! I've run into strange effect that I can not explain. I have simple expression that can be written by two equivalent ways. However one way give much performance gain over another. Here is an example: -- apply function many times (tail-recursive) many n f x = if n == 0 then x else many (n-1) f $! (f x) -- first adder function adder1 = let r = many 5000000 sin 1.0 in \x -> x + r -- second adder function adder2 = \x -> x + many 5000000 sin 1.0 main = do putStrLn $ show $ adder1 1 putStrLn $ show $ adder1 2 putStrLn $ show $ adder1 3 putStrLn $ show $ adder1 4 putStrLn $ show $ adder2 1 putStrLn $ show $ adder2 2 putStrLn $ show $ adder2 3 putStrLn $ show $ adder2 4 If you run program it think some seconds performing math, and them prints 4 results immediately. But with adder2 function, it perform calculation in every call, which can be seen visually. It seems that compiler is able to "cache" in some way long computation in first case, but not in second. I always thought that let a = b in x + a is just a syntactic sugar for x + b. Is it wrong? Of course, this is just a toy example. In reality I was writing run-time compilation. Suppose, you have an simple arithmetic expression with variables. data Expr = Var String | Add Expr Expr | Mul Expr Expr | ... type Env = Map.Map String Double compile :: Expr -> (Env -> Double) compile e = case e of Var n -> \env -> env Map.! n Add e1 e2 -> \env -> (compile e1) env + (compile e2) env Mul e1 e2 -> \env -> (compile e1) env * (compile e2) env .... The same thing occur here. Expressions (compile e1) and (compile e2) are re-evaluated every time when compiled expression is run with some environment. So, it is much more an interpretation than compilation. I want that compile function returns expression that are pre-evaluated as much as possible to maximally speed up subsequent evaluation in different environments. How can I force (compile e1) to be evaluated eagerly in case line for Add/Mul? P.S. I'm using GHC 6.6 on Debian Linux (x86 arch). With best regards, Alexander.

3 4

STM and random numbers
by Chad Scherrer 13 Jan '07

13 Jan '07

Hi, I'd like to be able to use randomIO, but I'm working within the context of STM. Is there a way to get these working together happily? For now, I guess I could kludgingly use unsafePerformIO inside STM (it's the other way around that's not allowed, right?), but I would need to be sure it doesn't get inlined. Thanks, Chad

9 10

MissingH: profiler support?
by Chris Eidhof 12 Jan '07

12 Jan '07

Hey all, I'm trying to profile my application, which makes use of MissingH. But when compiling with -prof -auto-all, I get the following error: > Language.hs:8:7: > Could not find module `Data.String': > Perhaps you haven't installed the profiling libraries for > package MissingH-0.18.0? > Use -v to see a list of the files searched for. When compiling without those options, everything works just fine. I built missingh from source, and added -prof -auto-all to GHCPARMS, and did a ./setup configure,make,install and still no result. Does anyone know what could be wrong? I'd really like to keep using MissingH and having profiling support at the same time. Thanks, -chris

6 10

building hare on ghc-6.6
by Yang 12 Jan '07

12 Jan '07

how do i build hare on ghc-6.6? after removing all references to package lang from myghc--make, i get: RefacUtils.hs:54:5: parse error on input `HasModName' this just seems like a normal class being exported. the makefile proceeds past this to build a bunch of other files fine. if i ignore this and try loading the emacs file and entering haskell-refac-mode on a .hs buffer i get: Can't exec program: /home/yang/tmp/pkg/pure/todo/HaRe_20012006/refactorer/pfe

2 1

advice on architecting a library (and haskell software in general)
by Yang 12 Jan '07

12 Jan '07

hi all, i'm looking for advice on how to architect a simple widget library for vty/hscurses, but these beginner-level questions should apply to haskell applications in general. input/requests on any aspect of my design would be greatly appreciated - in return perhaps you'll get something you'd actually want to use! i have studied in detail various haskell curses/vty apps, including yi, hmp3, riot, and hscurses.widgets/contactmanager. my immediate goal is to produce a set of composable widgets and a flexible framework that - as much as possible - reduces the amount of code a user has to write. my eventual goal is to make a functional gui library, along the lines of fruit/wxfruit/fg. to this end i've also read their literature, but i still do not understand enough about arrows/yampa/afrp. i currently have a tree of widgets, some of which can receive focus. this allows them to alter the program's key handling, but in a certain order based on the hierarchy. e.g., in my program, at the top-level, hitting either 'q' or 'f12' quits the program. when we focus on a container, pressing 'tab' will cycle focus among the subwidgets. when we focus on a text box, the key bindings layer, so that 'q' inserts a character into the text box, and 'f12' still exits and 'tab' still cycles focus. here's a simplified synopsis of the types (omits details like layout): class Widget w where output :: Bool {- whether we have focus -} -> w -> Output data Output = Output Image (Maybe CursorPos) KeyHandler type Image = [[(Char,Attr)]] -- Attr is just the text decoration (colors) type CursorPos = (Int,Int) type KeyHandler = ??? i'm guessing the most flexible type for KeyHandler could be Key -> IO (), but is this really the only/best approach? (every time i fall back to IO, i feel i'm missing something/a puppy dies/etc.) currently, this is what i have: type KeyHandler = Key -> AppState -> AppState -- maps to a state updater data AppState = AppState { rootWidget :: Widget, actualAppState :: ..., ... } but this has a number of apparent issues, including: - no decoupling of UI and app - that is, the key handlers that the widgets return have complete knowledge of the application state. so for instance, this particular text box knows that its key handler should be: handler key state = let oldPos = cursorPos $ someTextBox $ rootWidget $ state in case key of Left -> state { rootWidget { someTextBox { cursorPos = oldPos - 1 } } } ... - on key press, can't save to a file or otherwise do anything in IO. - this isn't going to scale - as my AppState grows and grows, we're throwing away and reconstructing a lot of state. and the coding style it demands is pretty clumsy, as demonstrated above. but if we switch to IO (): - still doesn't help decouple the library from the app. the above example key handling code snippet would be the same (i.e. still very clumsy), except that we'd be reading/writing the state from/to an IORef or MVar. - certainly, not all actions need IO. in fact, my current application is just a viewer, and thus needs no IO at all. - requires a global IORef or MVar - i don't know how to address the performance problem without resorting to sprinkling IORefs or MVars everywhere in the state structure, thus strangling the app into IO everywhere other open questions: - how should the "top-most" code work? currently, my app's main has a tiny event loop that feeds keys through a Chan to a State-ful function ([Key] -> State AppState [Image]) and then to the final drawing function ([Image] -> IO ()). however, depending on the resolutions to the above issues, this may radically change. - how should i compose the various key handlers? this, again, will depend. related work: yi/hmp3 also have one large piece of state in a global mvar (allows multiple threads to update it/trigger a redraw, instead of only redrawing in response to key events), with no attempt to decouple the UI and app parts of that state. event handling is done by a lexer that matches regex key patterns to IO () - this doesn't couple key handling with the UI components, and is thus not composable. (i thought the idea of using a lexer as the state automata was good - there may be some way to make this more composable, too, if the regex ever fails.) riot's UI code operates mostly in StateT Riot IO (), where Riot is again a monolithic application state. again, no attempt at decoupling or composability is made. hscurses.widgets operates mostly in IO (), and 'activating' (focusing) on widgets hands over the event loop completely. i hope i explained my design problems clearly. i've used haskell a bunch for various small text-processing scripts, but decided to try to use it for a "real" application that has little to do with parsing or other purported strengths of the language. i believe other new haskellers may relate to some of these issues. thanks! yang

2 1

CTRL+C in ghci.exe
by John Ky 12 Jan '07

12 Jan '07

Hi, Is it possible to use CTRL+C or equivalent to interrupt a computation or I/O and return to the ghci prompt? Thanks -John

4 4