January 2007 - Haskell-Cafe

class question
by Hans van Thiel 24 Jan '07

24 Jan '07

Hello, I'm trying to understand classes and defined: class Monoid a where e :: a add :: a -> a -> a add a e = a add e a = a instance Monoid a Int where e = 0 add x y = x + y This works just fine, also for instance definitions of Char, Bool and lists. But defining: class (Num a, Monoid a) => NumMon a where e = 0 add x y = x + y reults in error messages. -- Hugs: ERROR "Chap12.hs":57 - No member "e" in class "NumMon" -- GHCi: Chap12.hs:58:3: `add' is not a (visible) method of class NumMon' I've also tried instance definitions of NumMon (leaving out 'where' and what's next in the class declaration) and get similar messages. The definition of NumMon by itself, just the first line, is accepted by Hugs and GHCi both. What am I doing wrong? Many thanks in advance. Hans van Thiel

3 5

Re: [Haskell-cafe] Strings in Haskell
by Bryan Donlan 24 Jan '07

24 Jan '07

Neil Mitchell wrote: > Hi Alexy, > >> Now I'm reading a >> Haskell book which states the same. Is there a more efficient Haskell >> string-handling method? Which functional language is the most >> suitable for text processing? > > There are the Data.ByteString things, which are great, and have much > less overhead. > > But remember that Haskell is lazy. If you are thinking "well I have to > process a 50Mb file", remember that Haskell will lazily read and > process this file, which substantially reduces the memory requirements > so only a small portion will ever be in memory at a time. Or you can get the best of both worlds by using Data.ByteString.Lazy :) Even with laziness, all the indirections that String causes hurts performance.

3 2

small step evaluation as an unfold?
by Steve Downey 24 Jan '07

24 Jan '07

(overall context - working through TaPL on my own, reimplemnting typecheckers in haskell) the type checkers all follow the same pattern, in ocaml they throw an exception when the small step fails, which may mean taking another branch in the eval, but that that sub expression has hit bottom. it is self admittedly not good ocaml, and it seems to be even worse haskell, as i try to extend the simple evaluator i have to deal with managing reporting errors. having the single small step evaluator return a Maybe is fairly close. then the evaluator above it just bottoms out when eval1 expr returns Nothing, by passing expr back up as the result. but it occurs to me that it might be better to express it as an unfold, where the result is a list with the last element as the irresucible expression. or am i insane / intoxicated ?

2 2

Re: small step evaluation as an unfold?
by Steve Downey 24 Jan '07

24 Jan '07

good, it felt like something that might have occurred to someone before. On 1/23/07, Nicolas Frisby <nicolas.frisby(a)gmail.com> wrote: > Jeremy Gibbons thought of it; that's good company ;) > > http://portal.acm.org/citation.cfm?id=289457 > > > > On 1/23/07, Steve Downey <sdowney(a)gmail.com> wrote: > > (overall context - working through TaPL on my own, reimplemnting > > typecheckers in haskell) > > the type checkers all follow the same pattern, in ocaml they throw an > > exception when the small step fails, which may mean taking another > > branch in the eval, but that that sub expression has hit bottom. > > > > it is self admittedly not good ocaml, and it seems to be even worse > > haskell, as i try to extend the simple evaluator i have to deal with > > managing reporting errors. > > > > having the single small step evaluator return a Maybe is fairly close. > > then the evaluator above it just bottoms out when eval1 expr returns > > Nothing, by passing expr back up as the result. > > > > but it occurs to me that it might be better to express it as an > > unfold, where the result is a list with the last element as the > > irresucible expression. > > > > or am i insane / intoxicated ? > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > >

1 0

PDF library?
by Clifford Beshers 24 Jan '07

24 Jan '07

I don't suppose anyone has any Haskell code that understands the PDF format, do they?

4 3

embedding haskell into html
by Forest Liu 24 Jan '07

24 Jan '07

I am new to haskell, and now working on embedding haskell into html. Thus we will write webapp using haskell as server-side language like php. Here I explain my plan and ask some questions, looking for experienced ones to discuss with. It is not proper embedding lines of haskell code into html (like php). Because we would not know what to output, as it is not a procedural language as php. I think the proper way is using a single tag containing a haskell expression (usually a function name) each time of needing haskell. I call it "hasp" standing for "HASkell Page" :). It should look like: <html> <head><title><?hasp genTitle?></title></head> <body> ...some html... <?hasp getDataFromDB?> ...some html... </body> </html> And the functions ("genTitle", "getDataFromDB") should be implemented in "/same_dir_to_hasps/hs/same_name_to_each_hasp.hs" . It just like the templates in php. There are two possible ways to implementing the mechanism: compiled-CGI, and interpreting(or Just-In-Time Compilation) 1. Complied-CGI: use a preprocessor to combine the hasp templates and hs implementations, then compiled by ghc to generate cgi-bins. That should be easy for me to implement. 2.Interpreting (or JIT-Compilation) I prefer this method because modern web-scripting programmers should be familiar with it. The browser request for somepage.hasp, and Apache knows giving it to hasp interpreter to handle. I am facing to the dilemma between interpreting or JIT-Compilation. The best situation is a perfect haskell interpreting procedure written in haskell. I am trying hs-plugins, and I hope it will help me a lot. Or any other "haskell interpreting procedure written in haskell" you can tell me? The trouble about JIT-Compilation is that hasp-handler must call ghc through OS shell commandline using System.Cmd, and that is not proper in Apache cgi handler(lots of stuff to configure). BTW, if the "haskell interpreting procedure written in haskell" does not work well, I could use cmdline "ghc -e some_expr file.hs" to evaluate the expr, though an ugly way. And in that case, we would face to the problem of "external cmd of CGI" again. -- Sincerely, Forest Liu(��S)

2 1

catch the stdout when execute a shell cmd
by Forest Liu 24 Jan '07

24 Jan '07

I use "system" in System.Cmd to execute a shell cmd, then how can I catch its stdout? -- Sincerely, Forest Liu(��S)

2 1

GADTs are expressive
by Jim Apple 23 Jan '07

23 Jan '07

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. {-# OPTIONS -fglasgow-exts #-} {- Using GADTs to encode normalizable and non-normalizable terms in the lambda calculus. For definitions of normalizable and de Bruin indices, I used: Christian Urban and Stefan Berghofer - A Head-to-Head Comparison of de Bruijn Indices and Names. In Proceedings of the International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP 2006). Seattle, USA. ENTCS. Pages 46-59 http://www4.in.tum.de/~urbanc/Publications/lfmtp-06.ps @incollection{ pierce97foundational, author = "Benjamin Pierce", title = "Foundational Calculi for Programming Languages", booktitle = "The Computer Science and Engineering Handbook", publisher = "CRC Press", address = "Boca Raton, FL", editor = "Allen B. Tucker", year = "1997", url = "citeseer.ist.psu.edu/pierce95foundational.html" } -} module Terminating where -- Terms in the untyped lambda-calculus with the de Bruijn representation data Term t where Var :: Nat n -> Term (Var n) Lambda :: Term t -> Term (Lambda t) Apply :: Term t1 -> Term t2 -> Term (Apply t1 t2) -- Natural numbers data Nat n where Zero :: Nat Z Succ :: Nat n -> Nat (S n) data Z data S n data Var t data Lambda t data Apply t1 t2 data Less n m where LessZero :: Less Z (S n) LessSucc :: Less n m -> Less (S n) (S m) data Equal a b where Equal :: Equal a a data Plus a b c where PlusZero :: Plus Z b b PlusSucc :: Plus a b c -> Plus (S a) b (S c) {- We can reduce a term by function application, reduction under the lambda, or reduction of either side of an application. We don't need this full power, since we could get by with normal-order evaluation, but that required a more complicated datatype for Reduce. -} data Reduce t1 t2 where ReduceSimple :: Replace Z t1 t2 t3 -> Reduce (Apply (Lambda t1) t2) t3 ReduceLambda :: Reduce t1 t2 -> Reduce (Lambda t1) (Lambda t2) ReduceApplyLeft :: Reduce t1 t2 -> Reduce (Apply t1 t3) (Apply t2 t3) ReduceApplyRight :: Reduce t1 t2 -> Reduce (Apply t3 t1) (Apply t3 t2) {- Lift and Replace use the de Bruijn operations as expressed in the Urban and Berghofer paper. -} data Lift n k t1 t2 where LiftVarLess :: Less i k -> Lift n k (Var i) (Var i) LiftVarGTE :: Either (Equal i k) (Less k i) -> Plus i n r -> Lift n k (Var i) (Var r) LiftApply :: Lift n k t1 t1' -> Lift n k t2 t2' -> Lift n k (Apply t1 t2) (Apply t1' t2') LiftLambda :: Lift n (S k) t1 t2 -> Lift n k (Lambda t1) (Lambda t2) data Replace k t n r where ReplaceVarLess :: Less i k -> Replace k (Var i) n (Var i) ReplaceVarEq :: Equal i k -> Lift k Z n r -> Replace k (Var i) n r ReplaceVarMore :: Less k (S i) -> Replace k (Var (S i)) n (Var i) ReplaceApply :: Replace k t1 n r1 -> Replace k t2 n r2 -> Replace k (Apply t1 t2) n (Apply r1 r2) ReplaceLambda :: Replace (S k) t n r -> Replace k (Lambda t) n (Lambda r) {- Reflexive transitive closure of the reduction relation. -} data ReduceEventually t1 t2 where ReduceZero :: ReduceEventually t1 t1 ReduceSucc :: Reduce t1 t2 -> ReduceEventually t2 t3 -> ReduceEventually t1 t3 -- Definition of normal form: nothing with a lambda term applied to anything. data Normal t where NormalVar :: Normal (Var n) NormalLambda :: Normal t -> Normal (Lambda t) NormalApplyVar :: Normal t -> Normal (Apply (Var i) t) NormalApplyApply :: Normal (Apply t1 t2) -> Normal t3 -> Normal (Apply (Apply t1 t2) t3) -- Something is terminating when it reduces to something normal data Terminating where Terminating :: Term t -> ReduceEventually t t' -> Normal t' -> Terminating {- We can encode terms that are non-terminating, even though this set is only co-recursively enumerable, so we can't actually prove all of the non-normalizable terms of the lambda calculus are non-normalizable. -} data Reducible t1 where Reducible :: Reduce t1 t2 -> Reducible t1 -- A term is non-normalizable if, no matter how many reductions you have applied, -- you can still apply one more. type Infinite t1 = forall t2 . ReduceEventually t1 t2 -> Reducible t2 data NonTerminating where NonTerminating :: Term t -> Infinite t -> NonTerminating -- x test1 :: Terminating test1 = Terminating (Var Zero) ReduceZero NormalVar -- (\x . x)@y test2 :: Terminating test2 = Terminating (Apply (Lambda (Var Zero))(Var Zero)) (ReduceSucc (ReduceSimple (ReplaceVarEq Equal (LiftVarGTE (Left Equal) PlusZero))) ReduceZero) NormalVar -- omega = \x.x@x type Omega = Lambda (Apply (Var Z) (Var Z)) omega = Lambda (Apply (Var Zero) (Var Zero)) -- (\x . \y . y)@(\z.z@z) test3 :: Terminating test3 = Terminating (Apply (Lambda (Lambda (Var Zero))) omega) (ReduceSucc (ReduceSimple (ReplaceLambda (ReplaceVarLess LessZero))) ReduceZero) (NormalLambda NormalVar) -- (\x.x@x)(\x.x@x) test4 :: NonTerminating test4 = NonTerminating (Apply omega omega) help3 help1 :: Reducible (Apply Omega Omega) help1 = Reducible (ReduceSimple (ReplaceApply (ReplaceVarEq Equal (LiftLambda (LiftApply (LiftVarLess LessZero) (LiftVarLess LessZero)))) (ReplaceVarEq Equal (LiftLambda (LiftApply (LiftVarLess LessZero) (LiftVarLess LessZero)))))) help2 :: ReduceEventually (Apply Omega Omega) t -> Equal (Apply Omega Omega) t help2 ReduceZero = Equal help2 (ReduceSucc (ReduceSimple (ReplaceApply (ReplaceVarEq _ (LiftLambda (LiftApply (LiftVarLess _) (LiftVarLess _)))) (ReplaceVarEq _ (LiftLambda (LiftApply (LiftVarLess _) (LiftVarLess _)))))) y) = case help2 y of Equal -> Equal help3 :: Infinite (Apply Omega Omega) help3 x = case help2 x of Equal -> help1

6 9

Announce: Package rdtsc for reading IA-32 time stamp counters
by Martin Grabmueller 23 Jan '07

23 Jan '07

Hallo all, version 1.0 of package rdtsc has just been released. This small package contains one module called 'Rdtsc.Rdtsc'. This module provides the function 'rdtsc' for accessing the 'rdtsc' machine register on modern IA-32 processors. This is a 64-bit counter which counts the number of processor cycles since the machine has been powered up. Using this instruction, you can make very precise time measurements which are independent of the actual CPU frequency. But note that you can get strange results sometimes on a superscalar processor. A small program using this library looks like this: module Main where import Rdtsc.Rdtsc main = do t1 <- rdtsc t2 <- rdtsc putStrLn ("Cost of rdtsc (ffi call): " ++ show (t2 - t1)) Note that the Haskell foreign function interface imposes some additional overheads. On my machine, it takes about 950 cycles to call this function twice and to compute the difference, whereas in C the overhead is only about 84 cycles. The documentation for the package is available here: http://uebb.cs.tu-berlin.de/~magr/projects/rdtsc/ Download the source using darcs: darcs get http://uebb.cs.tu-berlin.de/~magr/darcs/rdtsc/ I would really like to get feedback on this little package, which already has been quite useful for me. Have fun and Happy Haskell Hacking in th New Year, Martin

6 7

Re: [Haskell-cafe] Strings in Haskell
by Alexy Khrabrov 23 Jan '07

23 Jan '07

I wonder if that's another reason OCaml is used in a(t least one) hedge fund -- why Jane St. preferred OCaml to Haskell, I wonder? Was it the state of affairs then that OCaml was more efficient (? -- WAGuess), and would they prefer Haskell now? I'm trying to make sense out of OCaml objects out of that already infamously annoying "Practical OCaml" book, and class object <blah>... doesn't look like much, not to say that "class object" sounds about as bad as most English in that book. (Written by an English major... What a decline in US education! :) I come from ML background, so Haskell laziness and OCaml objects are all new to me. But my Haskell book, Haskell School of Expression, is so much better written, that I'm reading it much faster. I'm CC'ing Yaron as his e-mail comes up in my Gmail context adwords on the word "Haskell." :) I'm interested in financial data mining and market modeling -- are there any good application of FP there, say in Lisp? Cheers, Alexy P.S. Somebody with an old-fashioned mail client please feel free to change the subject to "Financial Engineering with FP," gmail seems to etch its subjects in stone. :) On 1/23/07, Martin Jambon <martin_jambon(a)emailuser.net> wrote: > On Mon, 22 Jan 2007, Alexy Khrabrov wrote: > > > Greetings -- I'm looking at several FP languages for data mining, and > > was annoyed to learn that Erlang represents each character as 8 BYTES > > in a string which is just a list of characters. Now I'm reading a > > Haskell book which states the same. Is there a more efficient Haskell > > string-handling method? Which functional language is the most > > suitable for text processing? > > In OCaml, strings are compact sequences of bytes. And you can pass them > as-is to C functions: > > http://caml.inria.fr/pub/ml-archives/caml-list/2002/08/e109df224ff0150b3020… > > > Martin > > -- > Martin Jambon > http://martin.jambon.free.fr >

6 7