Re: [Haskell-cafe] functional graphs
Thomas Hartman wrote: I don't think this will work. From http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/src/Data-Graph-Inductive-Graph.html the minimal implementatin for Graph is -- | Minimum implementation: 'empty', 'isEmpty', 'match', 'mkGraph', 'labNodes' -- | Decompose a 'Graph' into the 'MContext' found for the given node and the -- remaining 'Graph'. match :: Node - gr a b - Decomp gr a b Basically, match given a node returns the graph minus the node, and a context for the node which has ingoing edges/labels, outgoing edges/labels, the node itself and the node label. With the operator you can compose these two things and get back your original graph. With the implementation you have described I can't see any way to implement this match function, unless per my above comment you're doing something weird like having no graph edges, or all possible graph edges. And then why use a graph? It's a _complete_ graph, i.e. there is an edge between every two nodes. I want to compute the minimum spanning tree using http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inductive-Query-MST.html without rewriting the FGL code and without generating the many edges explicitly. Eventually I want to have a proper tree (Data.Tree.Tree) for pre-order traversal. Preorder traversal of a MST gives a sub-optimal solution (not worse than twice as long as the optimum) for the travelling salesman problem (TSP). I may be on the wrong track, though. Thanks Christian Unless I'm missing something... Thomas. 2008/1/18, Christian Maeder [EMAIL PROTECTED]: Hi, Given a complete graph as a list of nodes whose edge labels are given by a function over two nodes: data CGraph a b = CGraph [a] (a - a - b) Can I define an instance for the fgl Graph class? import Data.Graph.Inductive.Graph instance Graph CGraph where empty = CGraph [] -- and now? I had no idea how to define empty (except using undefined). I thought of requiring a context for the node labels of type a, but this type is not mentioned in the class header. So it looked to me like the impossibility to define sets (requiring an Ord) as monads. (i.e. instance Monad Data.Set.Set) Any working proposals for my graph problem? Cheers Christian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] functional graphs
Benja Fallenstein wrote: However, if you'd be able to live with data CGraph a b = CGraph [LNode a] (Node - Node - b) then you should be able to write the instance like this-- instance Graph CGraph where empty = CGraph [] (const $ error Node not in graph) isEmpty (CGraph xs _) = null xs labNodes (CGraph xs _) = xs mkGraph nodes edges = CGraph nodes f where f x y = fromMaybe (error Edge not found) (lookup (x,y) edges') edges' = map (\(x,y,l) - ((x,y),l)) edges match x (CGraph nodes f) = case lookup x nodes of Nothing - (Nothing, CGraph nodes f) Just l - let nodes' = filter ((/= x) . fst) nodes left = map (\(y,_) - (f y x, y)) nodes' right = map (\(y,_) - (f x y, y)) nodes' in (Just (left, x, l, right), CGraph nodes' f) Thanks for pointing out this proposal. The actual problem is mkGraph that needs all the many edges created beforehand (that's what I wanted to avoid). Cheers Christian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Throwback of inferred types
Hello Jon, Monday, January 21, 2008, 1:18:52 AM, you wrote: You're missing out on a lot if this isn't available for Haskell yet. I didn't realise just how invaluable this is until a system upgrade broke it and I really struggled to write OCaml code without it: I don't know how I managed before! oh, yes, i have a really hard times debugging large chunks of new code. nothing works, ghc error messages are next to useless and the best thing i can do - is just to add type annotations everywhere in order to find where ghc and me thinks different -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] functional graphs
Hi Christian, On Jan 21, 2008 10:57 AM, Christian Maeder [EMAIL PROTECTED] wrote: Thanks for pointing out this proposal. The actual problem is mkGraph that needs all the many edges created beforehand (that's what I wanted to avoid). Well, uh, at the risk of being obvious, if you can avoid using fgl functions that call mkGraph, then there is nothing to say that mkGraph has ever to be called, and conversely, if you must use fgl functions that call mkGraph, then there is no way to avoid the fact that it gets the edge labels in a list... :-) A quick grep of the library shows that use of mkGraph is very rare. I haven't chased down the uses of functions that call mkGraph, though, so I don't really know whether many or few functions use mkGraph internally. Of course, you can use (mkGraph = error mkGraph) and see whether you trip over it at all. Best, - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec benchmarks
I think you should try again, the link is not dead. On Sun, 20 Jan 2008 21:54:08 +0100, Jon Harrop [EMAIL PROTECTED] wrote: I'd like to compare the performance of Parsec to other parsers but the only reference to a benchmark I have found is a dead link from one of the papers about Parsec: http://research.microsoft.com/users/daan/download/parsec/parsec.pdf Are there any surviving Parsec benchmarks? -- Met vriendelijke groet, Henk-Jan van Tuyl -- http://functor.bamikanarie.com http://Van.Tuyl.eu/ -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: Properties of optimizer rule application?
On Thu, 17 Jan 2008, Simon Peyton-Jones wrote: | To give a precise example: If I have a sequence of 'map's | map f0 . map f1 . ... . map fn | then there is some length where this is no longer collapsed to a single | 'map'? (a) GHC tries to do as much as possible in a single iteration of the simplifer; I think it uses an outermost-first strategy for this. (b) For each phase it runs the simplifier until nothing changes, or a maximum of N times, where N is settable by a command-line-flag -fmax-simplifier-iterations. After N it stops running that phase, even if the simplification has not terminated. This means that the simplifier follows a specific direction (outermost to inner or vice versa). I shall not rely on the order, but I must expect that there is an order, which restricts the application of rules. If it would really do as much as possible in a single iteration then there would be nothing left to do after one iteration, since the set of applicable rules remains the same within one phase. | However then I wonder, how it is possible to make the compiler to | go into an infinite loop by the rule | |loop forall x,y. f x y = f y x Yes, it's possible. Remember (a) does as much as possible, which in your rule means rather a lot. as much as possible in a particular order (which I shall not rely on), right? In this thread Roman and I have described stuff that isn't in the manual. Henning, would you feel like elaborating the Wiki page http://haskell.org/haskellwiki/GHC/Using_rules (which already has a lot of info) to reflect what you've learned? That way it's preserved for others. I have added many points and I hope I haven't made things more confusing as they are and I have set more links and added more articles to http://www.haskell.org/haskellwiki/Category:Program_transformation I think I also found a typo: http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html#phase-control The last line in the list, should certainly be NOINLINE[~k] f means: be willing to inline f until phase k, but from phase k onwards do not inline it. ^^ Recently I found that specialisation interacts in an unexpected way with explicit RULES (and with inlining). I used a function multiple times and this seemed to make GHC specialising this function (although I did not used a SPECIALISE pragma) to the particular type. But then this function was no longer available for fusion. It reminds me on the sharing problem - it is not always an optimization to share common sub-expressions. In this case the common sub-expression was a function which was used with the same type (thus same class dictionary) for each call. Also in one case declaring a function 'foo' as INLINE [0] avoided fusion of 'foo', where NOINLINE [0] did the fusion in phase 2. I assumed that these two pragmas are identical in phases before 0. Summarized I think it is not only required to have better control over the phases of the optimizer but to have a clear unifying concept of several kinds of program transformations, namely SPECIALISE, INLINE, RULES. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Hamming's Problem
Bertram Thanks for your help, I tried to solve the problem this weekend but I have some dudes. My reasoning is: The sequence is [1,a1,a2,a3,..] where a1 = h 1 1, a2 = h 1 a1, and so on So, I want to construct the list of lists [[1,a1,a2,a3], [h 1 1, h 1 a1, h 1 a2,..], [h a1 1, h a1 a1, h a1 a2,...] ... [h an 1, h an a2,h an a3,...] ... ] The function is hammingx = 1 : foldl1 merge [ map (h x) hammingx | x - hammingx] However this is not a solution because the list is a infinite list of infinite lists. Please some advices to resolve this problem. Thanks Jose Luis -Mensaje original- De: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] En nombre de Bertram Felgenhauer Enviado el: viernes, 18 de enero de 2008 8:36 Para: haskell-cafe@haskell.org Asunto: Re: [Haskell-cafe] Hamming's Problem Jose Luis Reyes F. wrote: Hi, In exercise 2 of http://www.walenz.org/Dijkstra/page0145.html we need to write a function that holds (1)The value 1 is in the sequence (2)If x and y are in the sequence, so is f(x,y), where f has the properties a. f(x,y) x b. (y1 y2) = (f(x,y1)f(x,y2)) This is a solution for this problem, but an inefficient one hammingff :: [Integer] hammingff = 1 : merge [ h x y | x - hammingff, y - hammingff ] [ h x y | y - hammingff, x - hammingff ] That's not sufficient. In fact, because hammingff is an infinite sequence, this is equivalent to hammingff = 1 : merge [ h (head hammingff) y | y - hammingff ] [ h x (head hammingff) | x - hammingff ] h x y = 2*x+3*y [snip merge function] Indeed, the first few terms of hammingff are [1,5,13,17,29], and the value h 5 5 = 25 is missing. anybody has a better solution?. I have some ideas, but maybe you want to work on a correct solution first? Btw, with your choice of h, the result list will contain all natural numbers that are not divisible by 3 and are = 1 (mod 4). Evaluating the first n elements of that list will require O(n^2) evaluations of h. Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe __ Informacisn de NOD32, revisisn 2805 (20080118) __ Este mensaje ha sido analizado con NOD32 antivirus system http://www.nod32.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: need help for cabal-install
Duncan, I got the latest cabal. The stack overflow is fixed. But the install command still does not work (on a very simple package). Attached is the verbose output. It does not like to proceed somewhere between configure and build. But the verbose is not telling why! I also attached my cabal dance with exactly the same configure options. /home2/ecoin/garden cabal install -v HTTP-Simple /home2/ecoin/ghc/bin/ghc --numeric-version looking for package tool: ghc-pkg near compiler in /home2/ecoin/ghc/bin found package tool in /home2/ecoin/ghc/bin/ghc-pkg /home2/ecoin/ghc/bin/ghc-pkg --version /home2/ecoin/ghc/bin/ghc -c /tmp/tmp26702.c -o /tmp/tmp26702.o /usr/bin/ld -x -r /tmp/tmp26702.o -o /tmp/tmp26703.o Reading installed packages... /home2/ecoin/ghc/bin/ghc-pkg list --global --user 'HTTP-Simple-0.1' is cached. Extracting /home2/ecoin/.cabal/packages/hackage.haskell.org/HTTP-Simple/0.1/HTTP -Simple-0.1.tar.gz to /tmp/TMPHTTP-Simple-0.1... Creating dist/setup (and its parents) /home2/ecoin/ghc/bin/ghc --make Setup.lhs -o dist/setup/setup -odir dist/setup - hidir dist/setup [1 of 1] Compiling Main ( Setup.lhs, dist/setup/Main.o ) Linking dist/setup/setup ... dist/setup/setup configure --verbose=2 --ghc --prefix=/home2/ecoin/htools --user cabal: Error: some packages failed to install: HTTP-Simple-0.1 Configuring HTTP-Simple-0.1... Warning: No build-type specified. If possible use build-type: Simple Preprocessing library HTTP-Simple-0.1... Building HTTP-Simple-0.1... [1 of 1] Compiling Network.HTTP.Simple ( Network/HTTP/Simple.hs, dist/build/Netw ork/HTTP/Simple.o ) /usr/bin/ar: creating dist/build/libHSHTTP-Simple-0.1.a Installing: /home2/ecoin/htools/lib/HTTP-Simple-0.1/ghc-6.6.1 Registering HTTP-Simple-0.1... Reading package info from dist/installed-pkg-config ... done. Saving old package config file... done. Writing new package config file... done. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hamming's Problem
Jose Luis Reyes F. wrote: Thanks for your help, I tried to solve the problem this weekend but I have some dudes. My reasoning is: The sequence is [1,a1,a2,a3,..] where a1 = h 1 1, a2 = h 1 a1, and so on So, I want to construct the list of lists [[1,a1,a2,a3], [h 1 1, h 1 a1, h 1 a2,..], [h a1 1, h a1 a1, h a1 a2,...] ... [h an 1, h an a2,h an a3,...] ... ] The function is hammingx = 1 : foldl1 merge [ map (h x) hammingx | x - hammingx] However this is not a solution because the list is a infinite list of infinite lists. Oh, but it's pretty close working, actually. We only need two small modifications: 1) use the right fold. foldl on an infinite list *never* produces a result. 'merge' is associative, so we can just use foldr instead: hammingx = 1 : foldr1 merge [map (h x) hammingx | x - hammingx ] 2) we still haven't exploited the property that h x 1 x. This property ensures that of the two arguments that 'merge' is applied to by 'foldr', the first one starts with the smaller element. So we can write merge' (x:xs) ys = x : merge xs ys hammingx = 1 : foldr1 merge' [map (h x) hammingx | x - hammingx] which actually works. I'd actually define 'hamming' as a higher order function: hamming :: Ord a = (a - a - a) - a - [a] hamming f a = result where result = a : foldr1 merge' [map (f x) result | x - result] hammingx = hamming h 1 HTH, Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] threads + IORefs = Segmentation fault?
On Sat, Jan 19, 2008 at 08:36:55PM +0100, Alfonso Acosta wrote: On Jan 19, 2008 2:36 PM, David Roundy [EMAIL PROTECTED] wrote: Using ghc 6.6, but I've since isolated the bug as being unrelated to the IORefs and threading, it was in an FFI binding that somehow never died until I was testing this new code. In case the you are creating a binding of haskell code. Did you make sure that the runtime constructor and destructor (hs_* functions) are properly called? The could be the source of the segfault. No, there are no bindings to haskell code involved. Perhaps it's even a segfault in libwww itself. -- David Roundy Department of Physics Oregon State University ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Newbie question
Hi, I try to undestand why this code dosen't work f :: (Num a)=Integer-a f i = i Integer is an instance of Num, so why does this code produce error: Couldn't match expected type 'a' againsta inferred type 'Integer' ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question
2008/1/21 Alexander Seliverstov [EMAIL PROTECTED]: Hi, I try to undestand why this code dosen't work f :: (Num a)=Integer-a f i = i Integer is an instance of Num, so why does this code produce error: Couldn't match expected type 'a' againsta inferred type 'Integer' ... But the type of this function says that it can return *any* instance of Num -- that is, the caller gets to choose which particular instance of Num they want. This function can only ever return an Integer. There is actually a function of this type, however; it's called fromIntegral. It works because it is a member of the Num type class. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ICFP2008 Call for Papers
Call for Papers ICFP 2008: International Conference on Functional Programming Victoria, BC, Canada, 22-24 September 2008 http://www.icfpconference.org/icfp2008 Submission deadline: 2 April 2008 ICFP 2008 seeks original papers on the art and science of functional programming. Submissions are invited on all topics from principles to practice, from foundations to features, from abstraction to application. The scope includes all languages that encourage functional programming, including both purely applicative and imperative languages, as well as languages with objects and concurrency. Particular topics of interest include * Applications and Domain-Specific Languages: systems programming; scientific and numerical computing; symbolic computing; artificial intelligence; databases; graphical user interfaces; multimedia programming; scripting; system administration; distributed-systems and web programming; XML processing; security * Foundations: formal semantics; lambda calculus; type theory; monads; continuations; control; state; effects * Design: algorithms and data structures; modules; type systems; concurrency and distribution; components and composition; relations to object-oriented or logic programming * Implementation: abstract machines; compile-time and run-time optimization; just-in-time compilers; memory management; parallel hardware; interfaces to foreign functions, services, components or low-level machine resources * Transformation and Analysis: abstract interpretation; partial evaluation; program transformation * Software-development Techniques: design patterns; specification; verification; validation; debugging; test generation; tracing; profiling * Functional Pearls: elegant, instructive, and fun essays on functional programming * Practice and Experience: novel results drawn from experience in education or industry. Experience Reports are also solicited, which are short papers (2-4 pages) that provide evidence that functional programming really works or describe obstacles that have kept it from working in a particular application. Functional Pearls and Experience Reports are separate categories of papers that need not report original research results and must be marked as such at the time of submission. Detailed guidelines on both categories are below. What's different this year? ~~~ * No double blind reviewing. Instructions for authors By Wednesday, 2 April 2008, 09:00 AM Apia time, submit an abstract of at most 300 words and a full paper of at most 12 pages (4 pages for an Experience Report), including bibliography and figures. The deadline will be strictly enforced and papers not meeting the page limits are summarily rejected. Authors have the option to attach supplementary material to a submission, on the understanding that reviewers are not expected to read it. A submission will be evaluated according to its relevance, correctness, significance, originality, and clarity. It should explain its contributions in both general and technical terms, clearly identifying what has been accomplished, explaining why it is significant, and comparing it with previous work. The technical content should be accessible to a broad audience. Each submission must adhere to SIGPLAN's republication policy, as explained on the web. Violation risks summary rejection of the offending submission. Proceedings will be published by ACM Press. Authors of accepted submissions are expected to transfer the copyright to ACM. They may have the option to have their presentation videotaped and published along with the conference proceedings in the ACM Digital Library. Video recordings will only be released at the consent of the presenter, which is expressed by signing an additional copyright release/permission form. Formatting ~~ Submissions must be in PDF format printable in black and white on US Letter sized paper and interpretable by Ghostscript. If this requirement is a hardship, make contact with the program chair at least one week before the deadline. ICFP proceedings are printed in black and white. It is permissible to include color in a submission, but you risk annoying reviewers who will have to decide if your final paper will be understandable without it. Papers must adhere to the standard ACM conference format: two columns, nine-point font on a ten-point baseline, with columns 20pc (3.33in) wide and 54pc (9in) tall, with a column gutter of 2pc (0.33in). A suitable document template for LaTeX is available from SIGPLAN. Submission ~~ Submissions will be accepted electronically; the submission page is not yet ready. The deadline is set at Samoan time, so if your submission is in by 09:00 AM Wednesday according to your local time,
Re: [Haskell-cafe] Data.Binary questions
Hi Derek,
Thanks for the reply.
On 20/01/2008, Derek Elkins [EMAIL PROTECTED] wrote:
You may want to consider using the other side of Data.Binary rather than
the Binary class. The -class- Binary is intended for de/serialization
when you don't care about the format. From the documentation:
For parsing and generating simple external binary formats (e.g. C
structures), Binary may be used, but in general is not suitable for
complex protocols. Instead use the Put and Get primitives directly.
Yes, you are right. I read that bit of the documentation, but didn't
understand how to use the Get and Put primitives. So I started by
using the Binary class and after getting quick results carried on with
it. I'll rewrite what I have with Get and Put once I figure out how
they actually work.
Nevertheless, one way to solve your problem is with a phantom type.
Change MyList to,
newtype MyList t e = MkList [e] deriving Show
getLengthType :: MyList t e - t
getLengthType = undefined
...
The asTypeOfs are just to propagate the type information around. GHC's
extension for scoped type variables would make this code simpler and
more direct. At any rate, now the code will use the Binary instance for
whatever type t is to serialize the length.
Ah, very clever. Is this a common idiom in Haskell?
If you mean that you there references to the constant table in e.g. the
fields table then the problem here is that you need to the class methods
to use that monad transformer (in this case, ReaderT is all you should
need and not even that), but you can't change their type. These are the
kind of issues that make the Binary class unsuitable for this type of
work. If that is the case, the only way to use this is to explicitly
write out the deserialization code rather than relying on get, i.e.
you'll have to write a function 'getTable constantTable' that will
deserialize the table.
As an example, a method is serialised in the class file as the
following structure:
method_info {
u2 access_flags;
u2 name_index;
u2 descriptor_index;
u2 attributes_count;
attribute_info attributes[attributes_count];
}
Both the name_index and the descriptor_index are indices that point
into the constants pool. In Haskell I would represent this as the type
data Method = Method Access String String [Attribute]
So I want to replace the indices with the actual strings that they
point to. I guess in the final deserialised version of the class file
the constant pool would not exist at all and it would be recreated
when the class file is serialised again.
So, AFAICT, I should be able to first deserialise the constants table
as part of deserialising the whole class file and then pass the
constant pool into the functions that deserialise fields, methods etc.
so that they are able to look up the constants from the pool.
I have to stare at the Get and Put primitives as well as ReaderT to
figure out how all this will work together. Let's call it a learning
experience.
--
! Lauri
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: functional graphs
Hello,
It's a _complete_ graph, i.e. there is an edge between every two nodes.
I want to compute the minimum spanning tree. Eventually I want to have a
sub-optimal solution for the travelling salesman problem (TSP).
A direct solution for this problem would be:
-- | place a f-minimal element to the left, remember the minimal value
min_left :: Ord b = (a - b) - [a] - ([a],b)
min_left _ [] = error min_left: empty list
min_left f (x:xs) = ms (x,f x) [] xs $ map f xs
where ms (y,v) nonmin (z:zs) (w:ws)
| w v= ms (z,w) (y:nonmin) zs ws
| otherwise= ms (y,v) (z:nonmin) zs ws
ms (y,v) nonmin _ _ = (y:nonmin,v)
-- | the same for cross xs ys and a f with arity two
mins :: Ord c = (a - b - c) - [a] - [b] - [(a, ([b],c))]
mins f xs ys =
fst $ min_left (snd . snd) [(x,min_left (f x) ys) | x - xs]
-- | *complete* graph
data CGraph a b = CGraph [a] (a - a - b)
-- | give a list of edges with weight that form a minimal spanning tree
prim :: Ord b = CGraph a b - [(a,a,b)]
prim (CGraph [] _) = []
prim (CGraph (x:xs) w) = build [x] xs
where build _ [] = []
build seen open =
let (f,(t:rest,v)):_ = mins w seen open
in (f,t,v) : build (t:seen) rest
-- | calculate the complete round trip and its (accumulated) weight
round_trip :: (Eq a, Ord b, Num b) = CGraph a b - [(a,a,b,b)]
round_trip = rt 0 [] . prim
where
rt _ [] [] = []
rt s ((c,r,v):bs) [] = (c,r,v,s+v) : rt (s+v) bs []
rt s [] ((r,c,v):ys) = (r,c,v,s+v) : rt (s+v) [(c,r,v)] ys
rt s (b@(z,t,w):bs) ((r,c,v):ys)
| r == z= (r,c,v,s+v) : rt (s+v) ((c,r,v):b:bs) ys
| otherwise = (z,t,w,s+w) : rt (s+w)bs ((r,c,v):ys)
{-
*Main round_trip $ CGraph [0..5] (\ x y - mod (x+y) 4)
[(0,4,0,0),(4,5,1,1),(5,3,0,1),(3,1,0,1),(1,3,0,1),(3,2,1,2),(2,3,1,3),(3,5,0,3),(5,4,1,4),(4,0,0,4)]
-}
Have fun!
/BR, Mirko Rahn
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Newbie question
Alexander Seliverstov [EMAIL PROTECTED] writes: How does caller choose which particular instance of Num they want? They specify the type... or just pass the result to something that specifies the type. Try it in ghci: Prelude let f:: Integral i = Integer - i; f = fromIntegral Prelude let g :: Int - Int; g = id Prelude :t g (f 5) g (f 5) :: Int Prelude let h :: Integer - Integer; h = id Prelude :t h (f 5) h (f 5) :: Integer Prelude What the difference between haskell class and interface in object-oriented languge such Java or C#? Really they are completely different animals that look a lot alike because they serve similar purposes -- convergent evolution! -- Jón Fairbairn [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question
How does caller choose which particular instance of Num they want? In object-oriented language If function return type is an interface it means that it can return any implementation of this interface, but caller can't choose which particular inplementation they want. What the difference between haskell class and interface in object-oriented languge such Java or C#? 2008/1/21, Brent Yorgey [EMAIL PROTECTED]: 2008/1/21 Alexander Seliverstov [EMAIL PROTECTED]: Hi, I try to undestand why this code dosen't work f :: (Num a)=Integer-a f i = i Integer is an instance of Num, so why does this code produce error: Couldn't match expected type 'a' againsta inferred type 'Integer' ... But the type of this function says that it can return *any* instance of Num -- that is, the caller gets to choose which particular instance of Num they want. This function can only ever return an Integer. There is actually a function of this type, however; it's called fromIntegral. It works because it is a member of the Num type class. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: Properties of optimizer rule application?
| I think I also found a typo: Quite right, thanks -- now fixed. | Recently I found that specialisation interacts in an unexpected way with | explicit RULES (and with inlining). I used a function multiple times and | this seemed to make GHC specialising this function (although I did not | used a SPECIALISE pragma) to the particular type. But then this function | was no longer available for fusion. Yes, specialisation generates new RULES. These new rules apply all the time, so they may rewrite your call to f before your fusion rules run. This is a bad thing. Really, specialisation should generate rules for a particular phase 'spec', and you should be able to add your fusion rules to precede or follow 'spec'. | Also in one case declaring a function 'foo' as INLINE [0] avoided fusion | of 'foo', where NOINLINE [0] did the fusion in phase 2. I assumed that | these two pragmas are identical in phases before 0. I'm not sure what is going on here | Summarized I think it is not only required to have better control over the | phases of the optimizer but to have a clear unifying concept of several | kinds of program transformations, namely SPECIALISE, INLINE, RULES. I can hardly argue with a clear unifying concept. But I'm not quite sure what you mean. Here's a stab. You could put this on the wiki and refine it with help from this end. * SPECIALISE generates a rule * RULES specifies a rule * INLINE is just like a rule (lhs = rhs) The latter two can be controlled to some extend by the phase mechanism. The first should be. Did you mean more than that? Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hangman game
On Jan 20, 2008, at 1:03 PM, Yitzchak Gale wrote: Generating an infinite list from a random generator burns up the generator, making it unusable for any further calculations. That's what the split function is for. ^_^ - Jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Newbie question
So, the function type (Num a)=Integer-a means that return value of this function can be cast to any particular instance of class Num. Ok. I have a my own class class A a and want to write function like this f:: (A a)=Integer-a. Can I do it? 2008/1/21, Jon Fairbairn [EMAIL PROTECTED]: Alexander Seliverstov [EMAIL PROTECTED] writes: How does caller choose which particular instance of Num they want? They specify the type... or just pass the result to something that specifies the type. Try it in ghci: Prelude let f:: Integral i = Integer - i; f = fromIntegral Prelude let g :: Int - Int; g = id Prelude :t g (f 5) g (f 5) :: Int Prelude let h :: Integer - Integer; h = id Prelude :t h (f 5) h (f 5) :: Integer Prelude What the difference between haskell class and interface in object-oriented languge such Java or C#? Really they are completely different animals that look a lot alike because they serve similar purposes -- convergent evolution! -- Jón Fairbairn [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- С уважением, Селиверстов Александр ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Newbie question
2008/1/21 Alexander Seliverstov [EMAIL PROTECTED]: So, the function type (Num a)=Integer-a means that return value of this function can be cast to any particular instance of class Num. Ok. I have a my own class class A a and want to write function like this f:: (A a)=Integer-a. Can I do it? Only if you make the function f a member of class A. Then it is the responsibility of each particular type which is an instance of A to define a way of converting an Integer into a value of that type. For example: class A a where f :: Integer - a ... other functions... instance A Integer where f = id instance A String where f = show and so on. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Yi and Data.ByteString
1) Can anyone tell me how I can build Yi or point me to a binary release of that editor? I tried to follow the instructions on http://www.nobugs.org/developer/yi/building.html but got a missing component error each time. 2) When if ever is Data.ByteString going to be the default string representation in GHC? I study computational linguistics and plan to switch to Haskell in the near future, that is once I get to grips with the language and the whole new thought model one has to develop as an imperative programmer. Best Regards, Cetin Sert www.corsis.de ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Yi and Data.ByteString
On Mon, 2008-01-21 at 19:12 +0100, Cetin Sert wrote: 1) Can anyone tell me how I can build Yi or point me to a binary release of that editor? I tried to follow the instructions on http://www.nobugs.org/developer/yi/building.html but got a missing component error each time. You need ghc-6.8.2, the latest yi from darcs darcs get http://code.haskell.org/yi as well as the latest version of fingertree and vty or gtk. If you have further question please use the yi-devel mailing list (http://groups.google.com/group/yi-devel). Note though, that yi is not ready for regular use, yet. But, of course, contributions are accepted anytime. 2) When if ever is Data.ByteString going to be the default string representation in GHC? Not anytime soon (if ever). It's not guaranteed to be faster in any case, but its generally faster for bigger inputs. If you're worried about literals, that's not a problem anymore. You can just use: myErrorMsg = Oops! :: ByteString I study computational linguistics and plan to switch to Haskell in the near future, that is once I get to grips with the language and the whole new thought model one has to develop as an imperative programmer. Good luck! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell web dev: Using Haskell and HAppS for Openomy API v2.0
A deployment of HAppS, AlexJ et al's web framework for Haskell, at openomy, The latest release of our API is written in Haskell using the new HAppS framework. The good news, Since being in production, we've so far found very few issues and everything runs quickly and smoothly. Haskell and HAppS have turned out to be a very nice addition to our stable of tools and services. See the review here, http://blog.openomy.com/2008/01/case-study-using-haskell-and-happs-for.html Congratulations to Alex, Musasabi, Shapr, Igloo, Lemmih et al who've worked on getting HAppS into the real world! :) -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Yi and Data.ByteString
On 2008.01.21 19:12:26 +0100, Cetin Sert [EMAIL PROTECTED] scribbled 1.9K characters: 1) Can anyone tell me how I can build Yi or point me to a binary release of that editor? I tried to follow the instructions on http://www.nobugs.org/developer/yi/building.html but got a missing component error each time. The specific error would help a lot. Also, yi-devel might be a good list to subscribe to. 2) When if ever is Data.ByteString going to be the default string representation in GHC? Not sure. I once asked about this, and it seems that ByteStrings don't support all the operations and definitions [Char] does; and there was mention of Unicode problems. Plus, ByteStrings aren't really built-in - they're a separate library. You could perhaps suggest that [Char] could be often optimized into ByteString operations but then ByteStrings need to either lose their library status and be incorporated into GHC or you need to expand the list of depended libraries... I wouldn't look for't anytime soon. I study computational linguistics and plan to switch to Haskell in the near future, that is once I get to grips with the language and the whole new thought model one has to develop as an imperative programmer. Well, you're not the first computational linguist. There are some pretty impressive projects in Haskell. Best Regards, Cetin Sert -- gwern argus ARPA garbage Internet Halliburton Corporation SASP disruptio Egret SLBM pgpElzgTK5Y4a.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Yi and Data.ByteString
Hello, On Mon, Jan 21, 2008 at 07:12:26PM +0100, Cetin Sert wrote: 2) When if ever is Data.ByteString going to be the default string representation in GHC? Why would you need such a thing? ByteStrings don't have any unicode support, and they can be quite slow for small strings. They are just a different tool for different task. But if you wish, you could use string literals as bytestrings with -XOverloadedStrings ghc (=6.8) flag Best Regards, Cetin Sert www.corsis.de -- pierre ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Draft chapters of Real World Haskell now publicly available
John, Don and I are pleased to announce the beginning of the public beta programme for our upcoming book, Real World Haskell. For further details, please see the following blog entry: http://www.realworldhaskell.org/blog/2008/01/21/finally-the-public-beta-programme-begins/ Thanks to all of the Haskell community members who have so far performed sterling service in commenting on our closed drafts. We look forward to your feedback! b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Binary questions
On Mon, 2008-01-21 at 16:18 +, Lauri Pesonen wrote:
Hi Derek,
Thanks for the reply.
On 20/01/2008, Derek Elkins [EMAIL PROTECTED] wrote:
You may want to consider using the other side of Data.Binary rather than
the Binary class. The -class- Binary is intended for de/serialization
when you don't care about the format. From the documentation:
For parsing and generating simple external binary formats (e.g. C
structures), Binary may be used, but in general is not suitable for
complex protocols. Instead use the Put and Get primitives directly.
Yes, you are right. I read that bit of the documentation, but didn't
understand how to use the Get and Put primitives. So I started by
using the Binary class and after getting quick results carried on with
it. I'll rewrite what I have with Get and Put once I figure out how
they actually work.
Nevertheless, one way to solve your problem is with a phantom type.
Change MyList to,
newtype MyList t e = MkList [e] deriving Show
getLengthType :: MyList t e - t
getLengthType = undefined
...
The asTypeOfs are just to propagate the type information around. GHC's
extension for scoped type variables would make this code simpler and
more direct. At any rate, now the code will use the Binary instance for
whatever type t is to serialize the length.
Ah, very clever. Is this a common idiom in Haskell?
Phantom types are a very common technique. They allow you to use the
static type system to enforce guarantees (and, in this case, generate
code). Essentially they let you add types to an untyped representation
giving you the benefits of both. Usually you can avoid doing the
asTypeOf chicanery I did.
If you mean that you there references to the constant table in e.g. the
fields table then the problem here is that you need to the class methods
to use that monad transformer (in this case, ReaderT is all you should
need and not even that), but you can't change their type. These are the
kind of issues that make the Binary class unsuitable for this type of
work. If that is the case, the only way to use this is to explicitly
write out the deserialization code rather than relying on get, i.e.
you'll have to write a function 'getTable constantTable' that will
deserialize the table.
As an example, a method is serialised in the class file as the
following structure:
method_info {
u2 access_flags;
u2 name_index;
u2 descriptor_index;
u2 attributes_count;
attribute_info attributes[attributes_count];
}
Both the name_index and the descriptor_index are indices that point
into the constants pool. In Haskell I would represent this as the type
data Method = Method Access String String [Attribute]
So I want to replace the indices with the actual strings that they
point to. I guess in the final deserialised version of the class file
the constant pool would not exist at all and it would be recreated
when the class file is serialised again.
So, AFAICT, I should be able to first deserialise the constants table
as part of deserialising the whole class file and then pass the
constant pool into the functions that deserialise fields, methods etc.
so that they are able to look up the constants from the pool.
I have to stare at the Get and Put primitives as well as ReaderT to
figure out how all this will work together. Let's call it a learning
experience.
As I hinted, ReaderT isn't really necessary either in this case. All it
amounts to is passing an extra parameter. In this case it is probably
clearer and simpler to explicitly pass the extra parameter, though you
can decide that for yourself.
Anyway, this documentation page may be more useful:
http://hackage.haskell.org/packages/archive/binary/0.4.1/doc/html/index.html
Basically your code will look similar to what it does now except instead
of using get you'll use getWord32le or whatever and your own functions
that will deserialize more involved structures, e.g. a getTable
function.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Newbie question
How does caller choose which particular instance of Num they want? By passing the type they want. That's what the Num a = thingy does. In object-oriented language If function return type is an interface it means that it can return any implementation of this interface, but caller can't choose which particular inplementation they want. The full type of f you've given is: forall a . (Num a) = Integer - a where the forall a . is normally not written. What you describe (a function that returns something where the type can be chosen by the function itself) would have type: Integer - (exists a . (Num a) = a) I.e. the a is not passed as a (type) argument, but instead it's returned by the function. What the difference between haskell class and interface in object-oriented languge such Java or C#? From a low-level point of view, the difference is that the vtable is manipulated separately from the objects. The Num a basically stands for the type of the vtable (which is called dictionary in Haskell). To bundle an object with its vtable as is traditionally done in OO languages, you need to create an existential package, e.g. something of type (exists a . (Num a) = a). Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Newbie question
Hey, I knew about the forall (I use that to represent OO style collections, very handy), but not about the exists. Thanks. But GHC 6.8.2 (with -fglasgow-exts) does not seem to accept this exists keyword? Does a book or document already exist (except the website) that tells more about not standarized yet very cool Haskell thingies that make writing real world applications possible? I would LOVE such a book. Cheers, Peter On Mon, 2008-01-21 at 16:10 -0500, Stefan Monnier wrote: How does caller choose which particular instance of Num they want? By passing the type they want. That's what the Num a = thingy does. In object-oriented language If function return type is an interface it means that it can return any implementation of this interface, but caller can't choose which particular inplementation they want. The full type of f you've given is: forall a . (Num a) = Integer - a where the forall a . is normally not written. What you describe (a function that returns something where the type can be chosen by the function itself) would have type: Integer - (exists a . (Num a) = a) I.e. the a is not passed as a (type) argument, but instead it's returned by the function. What the difference between haskell class and interface in object-oriented languge such Java or C#? From a low-level point of view, the difference is that the vtable is manipulated separately from the objects. The Num a basically stands for the type of the vtable (which is called dictionary in Haskell). To bundle an object with its vtable as is traditionally done in OO languages, you need to create an existential package, e.g. something of type (exists a . (Num a) = a). Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Draft chapters of Real World Haskell now publicly available
Oops, I just replied to another message asking for such a book! Amazing that my prayers are answered even before I asked them ;-) Peter On Mon, 2008-01-21 at 11:53 -0800, B ryan O'Sullivan wrote: John, Don and I are pleased to announce the beginning of the public beta programme for our upcoming book, Real World Haskell. For further details, please see the following blog entry: http://www.realworldhaskell.org/blog/2008/01/21/finally-the-public-beta-programme-begins/ Thanks to all of the Haskell community members who have so far performed sterling service in commenting on our closed drafts. We look forward to your feedback! b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Newbie question
On Mon, 2008-01-21 at 22:36 +0100, Peter Verswyvelen wrote: Hey, I knew about the forall (I use that to represent OO style collections, very handy), but not about the exists. Thanks. But GHC 6.8.2 (with -fglasgow-exts) does not seem to accept this exists keyword? That's because it isn't GHC syntax, Stefan was just using for demonstration purposes. (However, I think HBC does accept free existentials.) GHC does support local existentials (with two different syntaxes) and that's what you are probably using to make your OO style collections. When you write: data Foo = forall a.Foo (Num a = a) this is an -existential-. The type of (the data constructor) Foo is: Foo :: forall a.(Num a = a) - Foo The rules of logic give: Foo :: (exists a.Num a = a) - Foo note the change in scoping and compare this to local universal quantification: data Foo = Foo (forall a.Num a = a) Foo :: (forall a.Num a = a) - Foo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Draft chapters of Real World Haskell now publicly available
Bryan O'Sullivan [EMAIL PROTECTED] wrote: We look forward to your feedback! My browser shows me this: Dat geev en Fehler, as http://book.realworldhaskell.org/beta/funcstypes.html laadt wöör: Tiet op Server aflopen Verbinnen bestunn na book.realworldhaskell.org an Port 80 I think you have just been cafed. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Draft chapters of Real World Haskell now publicly available
Am Montag, 21. Januar 2008 20:53 schrieb Bryan O'Sullivan: John, Don and I are pleased to announce the beginning of the public beta programme for our upcoming book, Real World Haskell. For further details, please see the following blog entry: http://www.realworldhaskell.org/blog/2008/01/21/finally-the-public-beta-pro gramme-begins/ Thanks to all of the Haskell community members who have so far performed sterling service in commenting on our closed drafts. We look forward to your feedback! b Since my browser currently can't load http://book.realworldhaskell.org/beta/, what I found reading the first chapter comes this way. Overall: good style, nice contents. Operator precedence and associativity: the ghci command in question (and used in the example box) is :info, not :type. Lists: range notation: Range notation makes no sense for rational numbers, for example, because there is not a countable number of rationals. There are only countably many rational numbers, and we have instance (Integral a) = Enum (Ratio a) (with the same implementation as for Floating point numbers). The joy of it: When we couple 'it' with liberal use of the arrow keys to recall and edit the last expression we typed, and this gives us a fairly decent environment for interactive experiments, where the cost of mistakes is very low. That sentence is broken. One possible fix could be We can couple 'it' with liberal use of the arrow keys to recall and edit the last expression we typed. This gives us a fairly decent environment for interactive experiments where the cost of mistakes is very low. You can probably do better. I look forward to buying and reading that book:) Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Newbie question
Am Montag, 21. Januar 2008 21:55 schrieb Derek Elkins: On Mon, 2008-01-21 at 22:36 +0100, Peter Verswyvelen wrote: Hey, I knew about the forall (I use that to represent OO style collections, very handy), but not about the exists. Thanks. But GHC 6.8.2 (with -fglasgow-exts) does not seem to accept this exists keyword? That's because it isn't GHC syntax, Stefan was just using for demonstration purposes. (However, I think HBC does accept free existentials.) GHC does support local existentials (with two different syntaxes) and that's what you are probably using to make your OO style collections. When you write: data Foo = forall a.Foo (Num a = a) this is an -existential-. The type of (the data constructor) Foo is: Foo :: forall a.(Num a = a) - Foo I think you have a typo here. The type of the data constructor should be this: forall a. Num a = (a - Foo) The rules of logic give: Foo :: (exists a.Num a = a) - Foo note the change in scoping and compare this to local universal quantification: data Foo = Foo (forall a.Num a = a) Foo :: (forall a.Num a = a) - Foo Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: need help for cabal-install
On Mon, 2008-01-21 at 10:15 -0500, Steve Lihn wrote: Duncan, I got the latest cabal. The stack overflow is fixed. But the install command still does not work (on a very simple package). Attached is the verbose output. It does not like to proceed somewhere between configure and build. But the verbose is not telling why! I also attached my cabal dance with exactly the same configure options. /home2/ecoin/garden cabal install -v HTTP-Simple /home2/ecoin/ghc/bin/ghc --numeric-version looking for package tool: ghc-pkg near compiler in /home2/ecoin/ghc/bin found package tool in /home2/ecoin/ghc/bin/ghc-pkg /home2/ecoin/ghc/bin/ghc-pkg --version /home2/ecoin/ghc/bin/ghc -c /tmp/tmp26702.c -o /tmp/tmp26702.o /usr/bin/ld -x -r /tmp/tmp26702.o -o /tmp/tmp26703.o Reading installed packages... /home2/ecoin/ghc/bin/ghc-pkg list --global --user 'HTTP-Simple-0.1' is cached. Extracting /home2/ecoin/.cabal/packages/hackage.haskell.org/HTTP-Simple/0.1/HTTP -Simple-0.1.tar.gz to /tmp/TMPHTTP-Simple-0.1... Creating dist/setup (and its parents) /home2/ecoin/ghc/bin/ghc --make Setup.lhs -o dist/setup/setup -odir dist/setup - hidir dist/setup [1 of 1] Compiling Main ( Setup.lhs, dist/setup/Main.o ) Linking dist/setup/setup ... dist/setup/setup configure --verbose=2 --ghc --prefix=/home2/ecoin/htools --user So at this point configuring the HTTP-Simple package is failing without any error message. That's not so good. :-) cabal: Error: some packages failed to install: HTTP-Simple-0.1 So, for debugging, try configuring that package manually and see if the behaviour is the same and if so what the exit code is. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hangman game
I wrote: Generating an infinite list from a random generator burns up the generator, making it unusable for any further calculations. Jake McArthur wrote: That's what the split function is for. ^_^ Yes, that is a nice approach. I have been avoiding it due to the following comment in the docs for System.Random: This is very useful in functional programs... but very little work has been done on statistically robust implementations of split ([System.Random#Burton, System.Random#Hellekalek] are the only examples we know of). And my own experience has been that cases where I need split tend to be in a state monad anyway, where there isn't any real advantage to split. That said, looking around briefly, I came up with this paper by L'Ecuyer et al that does seem to describe a decent random generator with properties of split worked out: http://citeseer.ist.psu.edu/493863.html L'Ecuyer's implementations in C, C++ and Java are here: http://www.iro.umontreal.ca/~lecuyer/myftp/streams00/ If we had something like that in Haskell, I might use split more often. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hangman game
I wrote: That said, looking around briefly, I came up with this paper by L'Ecuyer et al that does seem to describe a decent random generator with properties of split worked out: Derek Elkins wrote: According to the documentation That -is- what we have. No, we have a much older algorithm of L'Ecuyer. It has a much smaller period - 2e18 vs. 3e51. Much less was known about testing generator randomness at that time. More importantly, very little was said in that paper about splitting. The newer algorithm includes all the computational details about splitting. Sadly, even the newer paper does not propose any tests for the independence properties of streams after splitting. The assumption seems to be that the voluminous testing of the underlying generator is sufficient for that also. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hangman game
On Tue, 2008-01-22 at 02:24 +0200, Yitzchak Gale wrote: I wrote: That said, looking around briefly, I came up with this paper by L'Ecuyer et al that does seem to describe a decent random generator with properties of split worked out: Derek Elkins wrote: According to the documentation That -is- what we have. No, we have a much older algorithm of L'Ecuyer. It has a much smaller period - 2e18 vs. 3e51. Much less was known about testing generator randomness at that time. Yeah, my fault. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Yi and Data.ByteString
-- Yi that's the error message I got following the instructions on http://www.nobugs.org/developer/yi/building.html setup: At least the following dependencies are missing: fingertree -any make: *** [dist/setup-config] Error 1 Where can I get fingertree from? Do I need a specific version of this package? -- Data.ByteString Where can I read more about GHC options like -XOverloadedStrings or this :: ByteString type declaration? I did not know ByteString was less performant than a linked list of characters. It is used even in the language shootout benchmark programs. Cetin On 21/01/2008, pierre [EMAIL PROTECTED] wrote: Hello, On Mon, Jan 21, 2008 at 07:12:26PM +0100, Cetin Sert wrote: 2) When if ever is Data.ByteString going to be the default string representation in GHC? Why would you need such a thing? ByteStrings don't have any unicode support, and they can be quite slow for small strings. They are just a different tool for different task. But if you wish, you could use string literals as bytestrings with -XOverloadedStrings ghc (=6.8) flag Best Regards, Cetin Sert www.corsis.de -- pierre ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hangman game
Achim Schneider wrote: Speaking of that, the generators that come in the box are awfully slow, I ended up calling into http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html via the ffi. Yes, it would be nice to have the Mersenne Twister available. Not only for speed - it is widely used, so it could sometimes be very useful for us to be able to generate random sequences that are bit-compatible with the sequences generated in other languages. I wouldn't know how to fit it into the Random type, though, it only supports floats and doubles, and converting the C source to use a struct for its data to make it instantiable is another obstacle. A few people worked all of that out. It's not a big deal. But it never was quite finished and put into the libraries. Yes, it is all the rage these days to do the calculations in floating point, due to the properties of current processors. It's not a problem to fit it into the RandomGen class - just convert to an Int when you're done. But that slows things down. Too bad the current Random class always forces you to go through Int. It was a good idea back then. We could fix this without breaking any current code. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Yi and Data.ByteString
cetin.sert: -- Yi that's the error message I got following the instructions on [1]http://www.nobugs.org/developer/yi/building.html setup: At least the following dependencies are missing: fingertree -any make: *** [dist/setup-config] Error 1 Where can I get fingertree from? Do I need a specific version of this package? -- Data.ByteString Where can I read more about GHC options like -XOverloadedStrings or this :: ByteString type declaration? I did not know ByteString was less performant than a linked list of characters. It is used even in the language shootout benchmark programs. It's not always slower or always faster. There's some particular operations where short [Char] is going to be faster than a pinned array. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Control.Concurrent.STM.old?
Hi, I don't think we included this in the version we checked in. It should be fairly easy to add to the current implementation: it will mirror ReadTVar except that the old value is always selected. I'm afraid I can't remember exactly why we didn't include it. One reason might have been that it would constrain alternative implementations -- for example one built over hardware transactional memory which might not necessarily provide access to the old state. Tim -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Thomas DuBuisson Sent: 19 January 2008 00:14 To: haskell-cafe@haskell.org Subject: [Haskell-cafe] Control.Concurrent.STM.old? Does the 'old' function referenced in the SPJ and Tim Harris data invariants paper stil exist? It is of type STM a - STM a and allowed invariants to compare old TVar values with new ones. I can't find it in any of the Haddocks or the code (and the 'check' funciton is not commented in the Haddock). Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hangman game
Thank you for the positive responses. The best kind of feedback is
the kind that makes me have to think, and I've done alot of thinking.
_Regarding monads and interfaces_
Paul Johnson wrote:
1: Your GameState type can itself be made into a monad. Take a look
at the All About Monads tutorial, especially the State
monad. Think about the invariants in GameState; can you produce a
new monad that guarantees these invariants through a limited set of
actions. How do these actions correspond to user perceptions?
2: You can layer monads by using monad transformers. Extend the
solution to part 1 by using StateT IO instead of just State.
OK, Here's the new monad and the corresponding transformer.
type Hangman = State GameState
type HangmanT = StateT GameState
And here's an interface for the Hangman monad.
newHangmanGame :: (MonadState GameState m) = String - m ()
newHangmanGame = put . newGameState
renderHangmanGame :: (MonadIO m, MonadState GameState m) = m ()
renderHangmanGame = get = return . renderGameState
= liftIO . putStrLn
guessLetter :: (MonadState GameState m) = Char - m ()
guessLetter = modify . handleGuess
getWonLost :: (MonadState GameState m) = m (Maybe Bool)
getWonLost = get = return . gsWonLost
getAnswer :: (MonadState GameState m) = m String
getAnswer = get = return . gsAnswer
This all seems a little pointless :) for a simple game, nevertheless I
proceeded to modify startNewGame and gameLoop to use the Hangman
interface. The modifications were trivial. The type signatures for
startNewGame and gameLoop become:
startNewGame :: HangmanT IO ()
gameLoop :: HangmanT IO ()
_Regarding random numbers_
Yitzchak Gale wrote:
You can add one more field to GameState that holds a random
generator.
I tried it; it was very easy.
Paul Johnson wrote:
Can you make your game a function of a list of random numbers?
Yitzchak Gale wrote:
I would advise against that technique. In more complex games, you
may need to do many different kinds of random calculations in
complex orders. Keeping a random generator inside a state monad is
perfect for that. And since Ronald already set up the plumbing for
the state monad, he is already home.
I simply modified startNewGame and gameLoop to accept a list of
integers. In startNewGame, I use the first integer in the list to
choose a word, and then I pass the rest of the list to gameLoop. In
gameLoop, I simply pass the list along to every recursive call to
startNewGame or gameLoop.
main :: IO ()
main = do
...
g - getStdGen
let rs = randomRs (0,length wordList - 1) g
runStateT (startNewGame rs) undefined
return ()
startNewGame :: [Int] - HangmanT IO ()
startNewGame (r:rs) = do
let word = wordList !! r
newHangmanGame word
renderHangmanGame
gameLoop rs
gameLoop :: [Int] - HangmanT IO ()
gameLoop rs = ...
I suppose I could easily push the list of random numbers into
GameState to avoid manually threading it around my program. If I did
that, then the only difference between the two techniques would be (1)
adding a field to hold a random number generator, vs (2) adding a
field to hold an infinite list of random numbers. If I store a list
of numbers, then I have to choose a probability distribution at
initialization time. If I store the generator, then I am free to
change the probability distribution on the fly.
For a Hangman game, the only time I need to change the probability
distribution is if I load a new word list. If I wanted to be able to
load a new word list, then perhaps I need to carry the word list
inside the GameState as well?
_Random numbers continued_
So let me create a HangmanRand monad to encapsulate the process of
selecting random words.
type HangmanRand = State RandState
type HangmanRandT = StateT RandState
data RandState = RandState {
rsRandGen :: StdGen,-- the random number generator
rsWordList :: [String] -- the word list
}
initHangmanRand :: (MonadState RandState m) = [String] - StdGen - m
()
initHangmanRand words g = put $ RandState{
rsRandGen = g,
rsWordList = words}
getRandomWord :: (MonadState RandState m) = m String
getRandomWord = do
rs - get
let words = rsWordList rs
let (n, g) = randomR (0,length words - 1) $ rsRandGen rs
put $ rs{rsRandGen = g}
return $ words !! n
I can easily modify the game to use HangmanRand. My gameLoop doesn't
have to change at all (apart from the type signature).
main :: IO ()
main = do
hSetBuffering stdout NoBuffering
putStr Welcome to Hangman!\n\n
putStr instructions
let seed = 5
let g = mkStdGen seed
runStateT (runStateT (initGame wordList g) undefined) undefined
return ()
initGame :: [String] - StdGen - HangmanT (HangmanRandT IO) ()
initGame words g = do
lift $ initHangmanRand words g
startNewGame
startNewGame :: HangmanT (HangmanRandT IO) ()
startNewGame = do
word -
Re: [Haskell-cafe] Haskell web dev: Using Haskell and HAppS for Openomy API v2.0
Indeed, from us at Openomy, we thank all those involved in HAppS for their work, and more importantly, their help with all our questions along the way. :) We're happy to answer any questions anyone may have on our experience, implementation, etc. Ian On 1/21/08, Don Stewart [EMAIL PROTECTED] wrote: A deployment of HAppS, AlexJ et al's web framework for Haskell, at openomy, The latest release of our API is written in Haskell using the new HAppS framework. The good news, Since being in production, we've so far found very few issues and everything runs quickly and smoothly. Haskell and HAppS have turned out to be a very nice addition to our stable of tools and services. See the review here, http://blog.openomy.com/2008/01/case-study-using-haskell-and-happs-for.html Congratulations to Alex, Musasabi, Shapr, Igloo, Lemmih et al who've worked on getting HAppS into the real world! :) -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ian Sefferman http://www.openomy.com | http://www.iseff.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] non-alphabetical mathematical symbols as non-infix function names
(¬) :: Bool → Bool (¬) q = not q q = True ¬ q : parser error on input q ¬ : parser error (possibly incorrect indentation) (¬ q) : Couldn't match expected type `Bool - t' against inferred type `Bool' In the expression: (� True) In the definition of `it': it = (� True) * (q ¬) : False (Why) is it not possible to define a (non-infix) function whose name consists of a single non-alphabetical mathematical symbol? ¬ :: Bool → Bool -- parser error on input ** ¬ q = not q -- parser error on input ** Cetin Sert ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Newbie question
Hello Alexander, Monday, January 21, 2008, 7:36:18 PM, you wrote: How does caller choose which particular instance of Num they want? In object-oriented language If function return type is an interface it means that it can return any implementation of this interface, but caller can't choose which particular inplementation they want. but type class isn't an interface! it's just like interface in one concrete area - it includes method specifications, but not includes data fields the type that should ìó returned by function is passed by means of so-called dictionary and which type should be returned is defined by type inference process. for example main = print (length [] + f 1) here f should return Int because length return Int and you can't add values of different types (without explicit type conversion). you should also read something about two-way type inference but i don't know any good source please note that in modern OOP languages (latest C# versions, C++ 0x) support for *one-way* type inference was only added, i.e. they only can deduce type of expression from types of operands, while Haskell deduces types in both directions -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Yi and Data.ByteString
Hello Cetin, Monday, January 21, 2008, 9:12:26 PM, you wrote: 2) When if ever is Data.ByteString going to be the default string representation in GHC? there is no need, you can just use it as any other type. having rich library is enough condition -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Newbie question
Hello Jon, Monday, January 21, 2008, 9:28:09 PM, you wrote: Ok. I have a my own class class A a and want to write function like this f:: (A a)=Integer-a. Can I do it? But in general you are going to want something a bit more useful, which means that you have to have a path from Integer to a i.e. you should have other functions that produce A from Integer and at the last end this means that class A should provide some way to do it -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
