Re: [Haskell-cafe] Substring replacements
Am Mittwoch, 21. Dezember 2005 15:20 schrieb Daniel Fischer: i'm 90% sure that straightforward method must be faster for one-time searches. I'm far less sure of that. If you have a really short search-pattern, I think that probably straightforward search is indeed faster (at least, if the search-pattern isn't supplied at compile-time). But if you have a pattern of length 100, say, and lots of relatively long partial matches, chances are that KMP will move on something like 50 chars at once, which would have to be re-checked by straightforward. I've no idea, when that would outweigh the extra time of building the KMP-arrays, though. In my test -- extremely unrealistic, but provides a more or less worst case example -- straightforward must make roughly half a million character comparisons to pass each 'c', while KMP does 2000 (+/-2) (one way through the array and back), so there are situations where KMP definitely is faster. But ordinarily, on my computer, your version of straightforward is 10-15% faster than KMP (search-patterns are now supplied on the command line -- which has no big impact; searched string is able sea...; all compiled with -O2; NOINLINE makes no difference -- at least with optimisations on --; without optimisations, KMP suffers far worse than straightforward). I've now tested with main = do args - getArgs n - case args of (ar:_) - readIO ar `catch` (\_ - return 400) _ - return 500 let src = replicate n 'r' dst = # str = replicate (n-1) 'r' ++ 'c': replicate n 'r' k = if n 200 then ceiling (5e6 / fromIntegral n) else ceiling (1e7 / fromIntegral n) out = searchReplace src dst $ concat $ replicate k str putStr Working with print n print $ length out putStrLn Done and KMP wins for n == 1 and n = 12, also for able seasea..., KMP wins for search-patterns of length 1 and patterns with no partial matches (and some others), but generally -- on my thing -- Bulat's version wins. Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: When to teach IO
Bayley, Alistair [EMAIL PROTECTED] writes: Hear, hear. Compilers, and computationally complex programs in general, are atypical. IMO, a lot of programming these days is integration work i.e. shuffling and transforming data from one system to another, or transforming data for reports, etc. Not many programmers write compilers these days :-( I'm sorry, but, if we define compiler as a input-process-output pipeline, then: shuffling and transforming data = compiler transforming data for reports = compiler I actually think a lot of useful programs fit into that category. (I certainly hesitate to accept the alternative, i.e. to admit that all my programs are useless :-) -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Arrows and pickler combinators
Folks,
I'm trying to monadify the pickler code. sequ below positively looks
like = but you can't really join both pickle and unpickle into a
single monad. I would like to keep the ops together, though, as this
allows me a single specification for both pickling and unpickling.
Cale suggested that PU is really an arrow in that it supports both
input and output. I could not find an example of such an arrow,
though. I thought that it could be a dual arrow but then could not
find a description for one.
I would appreciate your suggestions! The original paper is at http://
research.microsoft.com/ ~akenn/fun/picklercombinators.pdf
Thanks, Joel
P.S.
data PU a = PU
{
appP :: Ptr Word8 - Int - a - IO Int,
appU :: Ptr Word8 - Int - IO (a, Int),
appS :: a - IO Int
}
pickle :: PU a - Ptr Word8 - Int - a - IO Int
pickle p ptr ix value = appP p ptr ix value
unpickle :: PU a - Ptr Word8 - Int - IO (a, Int)
unpickle p ptr ix = appU p ptr ix
sizeup :: PU a - a - IO Int
sizeup p value = appS p value
lift :: a - PU a
lift x = PU (\_ ix _ - return ix) (\_ ix - return (x, ix)) (\_ -
return 0)
sequ :: (b - a) - PU a - (a - PU b) - PU b
sequ f pa k = PU
(\ptr ix b -
do let a = f b
pb = k a
ix1 - appP pa ptr ix a
appP pb ptr ix1 b)
(\ptr ix -
do (a, ix1) - appU pa ptr ix
let pb = k a
appU pb ptr ix1)
(\b -
do let a = f b
pb = k a
sz1 - appS pa a
sz2 - appS pb b
return $ sz1 + sz2)
pair :: PU a - PU b - PU (a,b)
pair pa pb = sequ fst pa (\ a - sequ snd pb
(\ b - lift $! (a, b)))
--
http://wagerlabs.com/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: When to teach IO
Ketil Malde writes: I'm sorry, but, if we define compiler as a input-process-output pipeline, then: shuffling and transforming data = compiler transforming data for reports = compiler I actually think a lot of useful programs fit into that category. Ketil, calling compiler all this stuff you mention, simply desintegrates the very definition of compilation. ALL is compiler... An image synthesis program (say, a ray-tracer like POV-Ray) is a compiler. TeX is a compiler. Etc. ... Perhaps, if you wish. But still, most people *USE* TeX or POV-Ray to make images or formatted documents. So, I think that your opponent (was it Alistair Bayley?) is mostly right claiming that people *write compilers* rarely. Even if I accept your philosophy that all/most data processing activities is a *kind* of compilation, in order to keep some minimum of discipline, I believe that it is good to assume that + Compilers are *universal*; they should handle a large set of sources, transforming them in something digested, reformatted, rendered visually etc. + The output of the compiler *should, at least conceptually* preserve the semantics - as we see it - of the source. Thus, say, a game is not a compiler. + They are more or less autonomous. TeX is a compiler. An add-on, say, a LaTeX macro-package (or an #included script to POV-Ray) are not, they just enrich the grammar of processed documents. + Compilers must respect some criteria of decency. (This is my idée fixe, I used to insist on that during all my compilation courses...) They are not allowed to break on erroneous data. They MUST terminate (gracefully). Etc. What is the percentage of programs written by average Norwegian salmon eaters which respect that? Concerning local French snail-eaters ... well, I lost all illusions quite a time ago. Jerzy Karczmarczuk PS. About the subject (when to teach IO): don't be sectarians. If a programming course insists on algorithmics, the IO issues can be postponed a bit. If it insists on practical data processing, IO should come in immediately. A programming course should be harmonious, homogeneous, well assembled, interesting, and easy to put into practice (...sorry for triviality, you ALL know that...), and the details depend on the language and on the teacher. In Scheme it is easier than in Haskell. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] When to teach IO
[mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED] PS. About the subject (when to teach IO): don't be sectarians. If a programming course insists on algorithmics, the IO issues can be postponed a bit. If it insists on practical data processing, IO should come in immediately. A programming course should be harmonious, homogeneous, well assembled, interesting, and easy to put into practice (...sorry for triviality, you ALL know that...), and the details depend on the language and on the teacher. In Scheme it is easier than in Haskell. _What_ is easier in Scheme than in Haskell? IO, or teaching (IO)? * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Tutorial uploaded
S Koray Can wrote: As a newbie... I agree that a newbie should be able to write this fairly early on: main = do x - getLine() putStrLn (The answer is ++ show(fib(read(x I'd agree for some definition of 'early'. I'll elaborate: [snip] The above code snippet contains typeclasses (show, read, monadic IO, lists), syntactic sugar (do, -). When you say a 'newbie' should be able to write that early on, I'd interpret that as 'a newbie should be able to regurgitate this early on' Well, I'm a newbie, and I wrote it. I have enough understanding to generate that code, even if I don't understand it all. This is what I know: * x is a string, fib wants an int, and read turns a string into a number. * The answer is is a string so you need ++. ++ expects a string, and show turns a number into a string. So, yes, I need *basic* knowledge of types (strings vs numbers) and the functions that convert from one to the other. But that's it. I don't need to know that do and - are syntactics sugar, or what a monad is (heck, I don't know those things). I think that the following is suitable for chapter 1: --//-- main = do putStrLn What is your name? name - getLine putStrLn(Hello ++ name) --//-- You don't need to learn about monads, or classes or lists for this. Yes, not even lists (Use ++ to catenate strings). All you need to know is strings, and that name - getLine gets a line from input and puts it in 'name'. I think that this is suitable for chapter 2: --//-- main = do putStrLn Please type a word: word - getLine putStrLn(This word has ++ (show( length word)) ++ letters) --//-- Here you learn about numbers, and converting numbers to strings (show). And this is for chapter 3: --//-- main = do putStrLn Please type a number: number - getLine putStrLn (number ++ ! = ++ (show (fac read(number))) --//-- Here you learn about converting a string to number. At some point between chapters 1 and 3 you'd learn how to write 'fac' (I guess chapter 1). Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/I am not over-weight, I am under-tall. / ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] When to teach IO
Bayley, Alistair asks (commenting my statement):
_What_ is easier in Scheme than in Haskell? IO, or teaching (IO)?
In my humble opinion, both. Mainly for psychological reasons,
we (well, we, students more than we, old Haskell cowboys...)
are used to the sequentiality of I/O. As people mentioned here,
even for a newbie there is no special hindrance to write a
do { ... putSomething ...}, especially if this newbie is a
faux-débutant, as the French say; if he/she has already some
acquaintance with other languages.
But, mind you, the teacher may want to convey the static nature of
functional programs first. The teacher may wish to *avoid* the
sequentiality issues, he may insist on expression-centered programming,
and then the IO in Haskell becames *another language*, different
from typical interactively tested recursive functions, all the stuff
you know.
That's it. In Scheme the integration of IO with the rest of the program
is more natural, you just have expressions with some side-effects, and
you accept that side-effects are natural.
Jerzy Karczmarczuk
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Tutorial uploaded
On 12/22/05, Daniel Carrera [EMAIL PROTECTED] wrote: S Koray Can wrote: As a newbie... I agree that a newbie should be able to write this fairly early on: main = do x - getLine() putStrLn (The answer is ++ show(fib(read(x I'd agree for some definition of 'early'. I'll elaborate: [snip] The above code snippet contains typeclasses (show, read, monadic IO, lists), syntactic sugar (do, -). When you say a 'newbie' should be able to write that early on, I'd interpret that as 'a newbie should be able to regurgitate this early on' Well, I'm a newbie, and I wrote it. I have enough understanding to generate that code, even if I don't understand it all. This is what I know: * x is a string, fib wants an int, and read turns a string into a number. * The answer is is a string so you need ++. ++ expects a string, and show turns a number into a string. Actually, it's a bit more than that (but still not harder than a newbie would be able to grasp in the first chapter). 'read' convertes a string into *any* readable value. So 'read (4,1.23,'c')' would convert a string into type '(Integer,Double,Char)'. Likewise 'show' converts any showable value to a string. This include numbers, but also includes a host of other values. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Tutorial uploaded
On 12/22/05, John Meacham [EMAIL PROTECTED] wrote: Just the idea that you can write things like mapM and replicateM is enough to blow the mind of many impertive programmers. Not trying to fan the flames, but one thing I struggle with is understanding (at a gut level - if you explain the theory, I'll understand, but go away none the wiser in practice...) why I need mapM as well as map (and all the other -M functions, liftM, foldM, etc...) mapM and so on really *are* why the IO monad is a great feature of Haskell. But the mental gearchange needed to appreciate what just happened is one of the speedbumps on the learning curve. You thought you were getting along fine, you'd got the point of functional stuff like map and fold, and you understood IO and it wasn't as scary as you'd thought. But then along comes mapM, and you're struggling again - why not just use map? And the explanation doesn't help much, it just leaves you feeling that you'd missed the point. As I say, I'm not trying to criticize anyone here, but it seems to be quite hard to get across to people who have understood and assimilated this sort of stuff, just how hard it feels to newcomers. We understand the explanations (we do! really! :-)) but even understanding them, we are still left with a lack of confidence. It's like being shown a full set of carpentry tools, having every one explained, but still reaching for the hammer every time and banging something no matter what we're trying to do :-) Paul. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Statements spanning multiple lines?
On 12/22/05, Daniel Carrera [EMAIL PROTECTED] wrote: Hi all, How do I write a statement that spans multiple lines? I have this function: pythagoras n = [(a,b,c) | a -[1..n], b -[1..n], c -[1..n], a = b, b c, a*a + b*b == c*c] This should all be in one line. I know some ways to make the line shorter, like defining local functions and using 'filter'. But the code would be clearer if I could just make this one statement span several lines. Indent the second line: pythagoras n = [(a,b,c) | a -[1..n], b -[1..n], c -[1..n], a = b, b c, a*a + b*b == c*c] /g -- We have lingered in the chambers of the sea By sea-girls wreathed with seaweed red and brown Till human voices wake us, and we drown. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Statements spanning multiple lines?
J. Garrett Morris wrote: Indent the second line: pythagoras n = [(a,b,c) | a -[1..n], b -[1..n], c -[1..n], a = b, b c, a*a + b*b == c*c] Thanks! Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/I am not over-weight, I am under-tall. / ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Statements spanning multiple lines?
Daniel Carrera wrote: Hi all, How do I write a statement that spans multiple lines? I have this function: pythagoras n = [(a,b,c) | a -[1..n], b -[1..n], c -[1..n], a = b, b c, a*a + b*b == c*c] This should all be in one line. I know some ways to make the line shorter, like defining local functions and using 'filter'. But the code would be clearer if I could just make this one statement span several lines. Haskell's layout rules mean that you have to keep intenting at the beginning of a line to continue a definition. Try something like... pythagoras n = [(a,b,c) | a - [1..n], b - [1..n], c - [1..n], a = b, b c, a*a + b*b == c*c ] ...or... pythagoras n = [(a,b,c) | a - [1..n], b - [1..n], c - [1..n], a = b, b c, a*a + b*b == c*c ] ...See also... http://www.haskell.org/onlinereport/lexemes.html#lexemes-layout Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Statements spanning multiple lines?
You might also like to try the slightly more efficient... pyth n = [(a,b,c) | a - [1..n], b - [a..n], c - [a+1..n], a*a + b*b == c*c ] Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Tutorial uploaded
On Thu, 22 Dec 2005, Paul Moore wrote: ... FWIW, I don't really see why the -M functions are needed either. It's something to do with the fact that map is for lists, and mapM is for monads, which are a more general type of sequence than a list. But why mapM isn't therefore a superset of map, and so map is redundant, I don't know. This reminds me why I like Hugs - whether I normally use it or not, I have it installed so that I can refer to lib/Prelude.hs, my single most useful Haskell document. You can offer any number of conceptual explanations of these things, but there seems to be no way to guarantee that they're going to be taken the right way. The Prelude definitions may or may not make sense, but at worst I don't think they can muddy the issue. I'm also reminded that there we're talking about several distinctly different types of learning here. If you're taking a class, you might well profit from a structured sequence that focuses on the static declarative aspects first, avoids recursion, etc. If you're on your own - as commonly the case with people reading tutorials - it's important to present the language in a useful form as soon as possible, let there be a temptation to switch to the Objective CAML tutorial because of a mistaken impression. Donn Cave, [EMAIL PROTECTED] --- sequence :: Monad m = [m a] - m [a] sequence [] = return [] sequence (c:cs) = do x - c xs - sequence cs return (x:xs) sequence_:: Monad m = [m a] - m () sequence_ = foldr () (return ()) mapM :: Monad m = (a - m b) - [a] - m [b] mapM f= sequence . map f mapM_:: Monad m = (a - m b) - [a] - m () mapM_ f = sequence_ . map f ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] exuberant-ctags, haskell, vim, tlist plugin
If you try a recent snapshot of cvs ghc, its ghci should support generating project-wide tags files for emacs and vim (btw, the online help for vim has another example of using tags for code browsing: showing the definition for the identifier under cursor in a preview window - very handy for data types;-). you'd still have to interface Tlist to haskell tags somehow, I guess? hth, claus - Original Message - From: Marc Weber [EMAIL PROTECTED] To: haskell-cafe@haskell.org Sent: Thursday, December 22, 2005 5:22 PM Subject: [Haskell-cafe] exuberant-ctags, haskell, vim, tlist plugin Hi. I'm a happy vim user and enjoyed using the Tlist plugin which shows only the methods and classes described in a file.. But it uses exuberant-ctags to parse the files which doesn't support haskell, yet. Has anyone already added haskell support? Is someone else interested? Other solutions perhaps another editor? Here are some screenshots of the tlist plugin for vim: http://www.geocities.com/yegappan/taglist/screenshots.html Marc ___ 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: Tutorial uploaded
On Thu, Dec 22, 2005 at 02:02:56PM +, Daniel Carrera wrote: I had never heard of mapM, or other -M functions. I can't imagine why those would be needed. It seems like pointless duplication. (!!!) then you are missing out. the M functions (and monadic traversal functions in general) especially when combined with the mtl are some of the best swiss army knives haskell has to offer. and it is map that is redundant. map f xs = runIdentity $ mapM f xs sequence = mapM id I have come to think of the monadic forms of these functions as the 'true' versions and the others as just common special cases. though, not my most common function used from the prelude, it is up there. and the most commonly used non-trivial function other than return: 922 mapM 937 Nothing 1017 not 1061 error 1433 String 1456 Just 1544 IO 1777 map 1810 show 1972 text 2595 Int 5303 return John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Statements spanning multiple lines?
Greg Buchholz wrote: You might also like to try the slightly more efficient... pyth n = [(a,b,c) | a - [1..n], b - [a..n], c - [a+1..n], a*a + b*b == c*c ] Cool. I'm amazed that actually works. I've been writing filters upon filters in all my functions because I didn't realize you could write things like that. Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/I am not over-weight, I am under-tall. / ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Tutorial uploaded
On 12/22/05, Daniel Carrera [EMAIL PROTECTED] wrote: Paul Moore wrote: As I say, I'm not trying to criticize anyone here, but it seems to be quite hard to get across to people who have understood and assimilated this sort of stuff, just how hard it feels to newcomers. We understand the explanations (we do! really! :-)) but even understanding them, we are still left with a lack of confidence. It's like being shown a full set of carpentry tools, having every one explained, but still reaching for the hammer every time and banging something no matter what we're trying to do :-) I had never heard of mapM, or other -M functions. I can't imagine why those would be needed. It seems like pointless duplication. mapM is like map except you map an IO Action over a list instead of a function of a list. For instance sizes - mapM getFileSize myListOfFileNames If you used map here you'd end up with a list of IO actions, and not a list of file sizes. You'd then have to go through this list of IO actions and using (-) on each element to get the file sizes. This can, incidentally, be done using the function 'sequence'. liftM lifts a function so that you can use a regular function on an IO Action instead of first having to extract the value of the IO action using (-). It's just shorthand, so you could do: x - liftM length (readFile afile) Instead of having to do f - readFile afile let x = length f The M functions really are useful, get to know them! /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Tutorial uploaded
SKC This entire discussion is about 'breaking a cyclic graph of conceptual SKC dependencies'. Unfortunately, I don't think it can be done well in short SKC amount of time. I bet if we sat down and listed all the concepts required to write idiomatic Haskell (even idiomatic Haskell 98 (whatever this means)), to write programs that do the things that we all have done in other languages (you know what I'm talking about here, but of course this is up for debate too), we would see that it was not a linear structure but a cyclic graph or at best a tree of concepts: we need to understand higher order functions, polymorphic higher order types for monads, monads to understand I/O really well (or to understand WHY I/O in a purely functional language is the way it is), typeclasses, laziness, etc. etc. In a lot of situations, pedagogy is hard to 'linearize'. Why would it be any different in programming? especially in Haskell? A lot of learning Haskell is just helping reinforce this strong, but sometimes subtle base of knowledge required to really start to get Haskell. [1] HT Btw. Simon Thompson states in his book, that he found it didactically HT infelicitous to introduce recursion before higher order functions because HT that let beginners stick to case discriminations and recursive programming HT instead of taking advantage of functions like 'map', 'iterate', 'fold' HT etc. I can confirm this experience and I think that it is similar to IO HT vs. non-IO. It very well may be didactically infelicitous [2]. (I wish there were some program we can just run on a course syllabus and find out that something is felicitous): conceptsInHaskell :: [haskellConcept] conceptsInHaskell = [...] -- abstract main = print $ sort conceptsInHaskell .. error: haskellConcept not a member of class Ord. Maybe we'll (collectively) get better and better at this. I think we are. Hopefully experience and sharing this information will be beneficial to all (as well as discussion like these). Maybe it depends on who is learning Haskell, and why: maybe the 'conflict' is that learning to program *in* Haskell /= learning to program *with* Haskell. But maybe it's not ultimately an optimizable piece of data, the right order of teaching concepts in Haskell. Maybe it should be allowed to be more random-access? (I personally like things more that way :-) . Cheers Jared. -- [EMAIL PROTECTED] http://www.updike.org/~jared/ reverse )-: [1] Perhaps a point in Haskell's favor for pedagogy is that there are things you can do in Haskell that you just can't do (in the same, succint sense) in most programming languages, e.g. even OCaml. Maybe these things (and they are neat, simple things, like the code twos = 2:twos and then manipulating this infinite stream) can help motivate people to really want to grok Haskell, and to stick with it and use it for practical projects because of its many advantages. :-) [2] Paul Hudak does this in the Haskell School of Expression. He writes recursive code with cases, etc. and then in a later chapter explains how to rewrite it with map, fold, etc. Fine. It takes steps to learn how to write idiomatic Haskell. At least for me, the joy of Haskell is not in memorizing vocabulary (as is common in a language like Java, or C#) but rather, internalizing concepts. By writing ugly code at first and then seeing the patterns and refactoring with map and fold, I've personally internalized it (instead of learning some clever rule, up front, that I'll later forget). Think Why FP Matters by Hughes. He does this too (recursion, pattern matching, then later swapping in higher order functions), to explain why FP is so great. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] FAQ: Why no interactive definitions?
In neither GHCi nor Hugs (so far as I know) is it possible to interactively enter definitions. coming from Scheme, this was a bit of a surprise, as I'm used to being able to enter, say (define mysquare (lambda (x) (* x x))) Is this just a matter of the feature not being implemented, or is there a deeper reason for this? === Gregory Woodhouse [EMAIL PROTECTED] Interaction is the mind-body problem of computing. --Philip L. Wadler ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] FAQ: Why no interactive definitions?
In ghci at least, you can enter definitions like that using let binding: let mysquare x = x * x /g On 12/22/05, Greg Woodhouse [EMAIL PROTECTED] wrote: In neither GHCi nor Hugs (so far as I know) is it possible to interactively enter definitions. coming from Scheme, this was a bit of a surprise, as I'm used to being able to enter, say (define mysquare (lambda (x) (* x x))) Is this just a matter of the feature not being implemented, or is there a deeper reason for this? === Gregory Woodhouse [EMAIL PROTECTED] Interaction is the mind-body problem of computing. --Philip L. Wadler ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- We have lingered in the chambers of the sea By sea-girls wreathed with seaweed red and brown Till human voices wake us, and we drown. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] FAQ: Why no interactive definitions?
There was a good discussion about this on an earlier thread. http://www.mail-archive.com/haskell-cafe@haskell.org/msg11372.html In fact, this exact question sparked a number of long threads. :-) (First steps in Haskell, Tutorial upload, Proposal for a First Tutorial.) Cheers, Jared. -- [EMAIL PROTECTED] http://www.updike.org/~jared/ reverse )-: ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: HDBC 0.6.0
Hello, Version 0.6.0 of HDBC and the Sqlite3 bindings are now available. New features since Tuesday's 0.5.0 announcement include: * New type system for marshalling different Haskell types back and forth * New support for querying meta-information about the server * Much improved documentation * Fix for a race condition in the Sqlite3 binding * New fetchAllRows function that returns a lazy list of result rows (think hGetContents for database queries) I will shortly begin work on a PostgreSQL binding. Also, I plan to write a MissingH interface module. The main idea of that is to provide a SQL backend for the MissingH AnyDBM interface (which uses *dbm databases for persistent hashes). Combined with Sqlite, this provides a very interesting and easy to use persistent hash interface. -- John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Arrows and pickler combinators
At Thu, 22 Dec 2005 11:26:51 +,
Joel Reymont wrote:
Folks,
I'm trying to monadify the pickler code. sequ below positively looks
like = but you can't really join both pickle and unpickle into a
single monad. I would like to keep the ops together, though, as this
allows me a single specification for both pickling and unpickling.
Last weekend, I hacked up a pickling/unpickling library of my own. The
code is currently a little confusing because I decided to change the
naming scheme half way through. So, don't assume to much from the
names of things.
darcs get http://www.n-heptane.com/nhlab/repos/BerkeleyDB
The file you are interested in is Binary.hs.
-== Short Summary ==-
My library splits the pickling into two parts you can mix and match.
(1) the part that turns a value into a byte stream
(2) the part that reads/writes values from/to the byte stream
-== Core of pickler ==-
My pickling/unpickling code is based around the data type:
data BinParser state m a = BinParser { runBinParser :: state - m (a, state) }
This type is used for both pickling and unpickling (the type needs a
better name). It is abstracted over three types:
state - for the pickler, state will hold the data that has currently been
pickled.
for the unpickler, state will hold the data to unpickle.
m - a monad of your choice
a - the value being pickled/unpickled
The reason for abstracting over state is to allow you to pickle
directly to [Word8], Ptr Word8, or whatever else you wish to
implement. Some times a monad my be needed for reading/writing the
state. For example, Ptr Word8 requires the IO monad. If you don't
really need a monad, then the Identity monad can be used.
-== BinParser Monad Instance ==-
The monad instance for BinParser is pretty straight-forward:
-- A monad instance for BinParser
instance (Monad m) = Monad (BinParser state m) where
return a = BinParser (\s - return (a, s))
bp = f = BinParser ( \state -
do (a, state') - runBinParser bp state
runBinParser (f a) state'
)
As I mentioned before, BinParser is used for both pickling *and*
unpickling. Normally we think of Parsers as consuming the state, but
there is no reason the 'parser' can not instead produce the state.
Also, note that this monad instance is not very specific to
pickling/unpickling at all. It is pretty much just a state monad. As a
matter of fact, I hope to be able to switch to Control.Monad.State
when I have time to work on this again.
-== Adding new 'states' to pickle/unpickle ==-
To add a new type of state to pickle/unpickle, you just add a new
instance to this class (once again, needs a better name):
class (Monad m) = BinState s m where
getWord8 :: BinParser s m Word8
putWord8 :: Word8 - BinParser s m ()
For example:
instance BinState (Ptr Word8) IO where
getWord8 = BinParser $ \p - do v - peek p
return (v, advancePtr p 1)
putWord8 w = BinParser $ \p - do poke p w
return ((), advancePtr p 1)
-== pickle vs. unpickle ==-
Here is where we actually combine the above to do pickling (once
again, naming should be updated):
class ToBin state m a where
binary :: a - BinParser state m ()
unbinary :: BinParser state m a
Here is a simple pickler for 'Char'
-- May want to store as 4 bytes to support Unicode later.
instance (BinState state m) = ToBin state m Char where
binary c = putWord8 (fromIntegral (ord c))
unbinary =
do w - getWord8
return $! (chr (fromIntegral w))
Here is a pickler for lists that shows the monad usage a bit better:
instance (BinState state m, ToBin state m a) = ToBin state m [a] where
binary l =
do binary (length l)
mapM_ binary l
unbinary = getList
getList :: (BinState state m, ToBin state m a) = BinParser state m [a]
getList =
do len - getInt
replicateM len unbinary
-== User Friendly Interface ==-
binary/unbinary are not very user friendly interfaces, so we also
define some user friendly interefaces. If I switched to
Control.Monad.State, I could just use the similar interfaces defined
there...
pickleM/unpickleM is useful if your state requires a monad.
-- NOTE: you may need to force the type to get this to work
-- eg. pickleM hi :: IO [Word8]
pickleM :: (Monad m, ToBin state m a) = state - a - m state
pickleM initState a =
do (_,finalState) - (runBinParser (binary a) initState)
return finalState
-- NOTE: you may need to force the type to get this to work
-- eg. fromBin (unPickleM hi :: [Word8]) :: IO String
unpickleM :: (Monad m, ToBin state m a) = state - m a
unpickleM state =
do (a,_) - runBinParser unbinary state
return a
pickle/unpickle are useful if your state does not need a monad.
-- Some pickler's may not need to run inside a monad, in which case we
-- can use these varients to avoid
[Haskell-cafe] Encapsulation in Haskell
Hi guys, So one of the big things in object oriented programming is encapsulation, and I'm wondering how to do it properly in Haskell. How do you define new data types but minimize the dependence of external packages on the exact nature of the data definition? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type inference for infinite structures
Hi everyone, I'm relatively new to Haskell and was a bit troubled by the problem of assigning a type to infinite structures. To give a clear example, suppose we have data Nat = Zero | Succ Nat omega = Succ omega What type then does omega have? According to GHCi, omega :: Nat. But surely this can only be the case if we already have that omega :: Nat (on the right hand side of the equation)? I can see that the type assignment is valid, but is it necessarily the case? Does it not, somehow, sidestep the inductive base case of the definition of a Nat? Thanks, Matt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type inference for infinite structures
On 12/23/05, Matt Collins [EMAIL PROTECTED] wrote: Hi everyone, I'm relatively new to Haskell and was a bit troubled by the problem of assigning a type to infinite structures. To give a clear example, suppose we have data Nat = Zero | Succ Nat omega = Succ omega What type then does omega have? According to GHCi, omega :: Nat. But surely this can only be the case if we already have that omega :: Nat (on the right hand side of the equation)? I can see that the type assignment is valid, but is it necessarily the case? Does it not, somehow, sidestep the inductive base case of the definition of a Nat? omega :: Nat so, Succ omega :: Nat, as well (see the second constructor in the data type Nat). So there is no ambituity. Succ requires that its argument is of type Nat, and the result of applying Succ to a Nat is also of type Nat. It's hard to explain this better than that, I think you've just got stuck in some mental barrier. I think the a good track to start thinking in would be to consider that the type inference starts with the type of Succ (which is Nat-Nat), given that we know that its argument is Nat, and that the result is Nat, so the left hand side must also be Nat. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Tutorial uploaded
Paul Moore wrote: Not trying to fan the flames, but one thing I struggle with is understanding (at a gut level - if you explain the theory, I'll understand, but go away none the wiser in practice...) why I need mapM as well as map (and all the other -M functions, liftM, foldM, etc...) All you really need to understand is what sequence :: Monad m = [m a] - m [a] does. Once you get that, the difference between map and mapM is clear because of mapM f xs = sequence (map f xs) Udo. -- Worrying is like rocking in a rocking chair -- It gives you something to do, but it doesn't get you anywhere. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: kinds question
David Roundy wrote: Hello all, I have a question about how to create the right kind to declare lists to be a class. I have a class Foo class Foo f where foo :: f a - Foo and I want to define that a list of Foos is also a Foo, but can't see how to do it. I imagine something like instance Foo f = Foo [f] where foo xs = map foo xs but of course [f] isn't a valid type. [] and f both have * - *, and you want to compose them. You can do this like this: newtype Compose p q a = MkCompose p (q a) and then instance Foo f = instance (Compose [] f) where foo (MkCompose fs) = ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type inference for infinite structures
Thanks Sebastian, I guess I was ignoring the type of Succ like you said. Glad to have passed that mental barrier! On 23/12/2005, at 12:14 PM, Sebastian Sylvan wrote: On 12/23/05, Matt Collins [EMAIL PROTECTED] wrote: Hi everyone, I'm relatively new to Haskell and was a bit troubled by the problem of assigning a type to infinite structures. To give a clear example, suppose we have data Nat = Zero | Succ Nat omega = Succ omega What type then does omega have? According to GHCi, omega :: Nat. But surely this can only be the case if we already have that omega :: Nat (on the right hand side of the equation)? I can see that the type assignment is valid, but is it necessarily the case? Does it not, somehow, sidestep the inductive base case of the definition of a Nat? omega :: Nat so, Succ omega :: Nat, as well (see the second constructor in the data type Nat). So there is no ambituity. Succ requires that its argument is of type Nat, and the result of applying Succ to a Nat is also of type Nat. It's hard to explain this better than that, I think you've just got stuck in some mental barrier. I think the a good track to start thinking in would be to consider that the type inference starts with the type of Succ (which is Nat-Nat), given that we know that its argument is Nat, and that the result is Nat, so the left hand side must also be Nat. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] zigzag data structure
I'm curious what this user community would come up with in order to
implement the curious zigzag data structure. If you haven't heard
anything about it, its a simple but peculiar idea, by the guy who
dreamed up the Xanadu project: http://xanadu.com/zigzag/.
Conceptually it is cells with some sort of value, where each cell
has any number of connections to any other cell, but the connections
are conceptually labeled/grouped as though they were dimensions. So a
cell with the value Brian McQueen would have a link to dorky guy
in the Description dimension, and a link to 519 S. Frances in the
Street Address dimension. Obviously most people would have links in
those same dimensions passing through their own name's cell. My cell
might have a pointer to Hector in the Hero dimension while a
conceited man might have a link right back to itself in that same Hero
direction. So the structure is very flexible. There are interesting
examples on the web site of a Day Planner type of an app where each
day has a time line and each time has appointments and the
appointments have attendees and they all have personal contact
information ... But its all logically linked.
I imagine it would be something like this in C-like code:
struct cell { value; ptr_to_links };
struct link { { dimension; ptr_to_destination; ptr_to_link; };
struct dimension { name; id; } ;
As I write this I realise that I don't remember much, if any,
discussion in this group about data structures. I may be starting
with a non-functional way of thinking.
BTW I'm mostly still at the reading Haskell and fiddling with ghci phase.
Brian McQueen
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] zigzag data structure
That sounds like a special case of what is called a graph in
mathematics and computer science.
See:
http://en.wikipedia.org/wiki/Graph_%28mathematics%29
and
http://en.wikipedia.org/wiki/Graph_%28data_structure%29
Essentially, the structure that they define on that site is a graph
with arcs labelled in such a way that any vertex has at most one
outgoing arc with that label (and hence at most one incoming arc with
that label as well).
There are a number of graph libraries for Haskell, including two which
come with GHC. The relevant modules are Data.Graph and
Data.Graph.Inductive(.*), the latter of which is quite extensive
(though many of the identifiers it exports are unfortunately poorly
named).
Data declarations in Haskell allow you to define recursive data
structures, but graphs are not quite so directly represented from that
perspective. Normally, one thinks of a graph as a set of vertices,
together with a set of edges. A number of tactics for storing these
sets can be considered -- from using balanced binary trees, to arrays,
to an inductive trace of the graph structure, building it up, one
vertex, together with a collection of adjacent edges at a time.
For a better explanation of that last view, which by no coincidence at
all happens to be the one that Data.Graph.Inductive uses, see:
Inductive Graphs and Functional Graph Algorithms
http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01
For set and finite map types, see Data.Set and Data.Map, which are
very well designed libraries for those purposes. There are also
arrays, both immutable and mutable, see Data.Array.IArray and
Data.Array.MArray respectively for the abstract interfaces to these,
and the surrounding modules for implementations with a wide variety of
characteristics.
The documentation for the hierarchical libraries included with GHC is at:
http://www.haskell.org/ghc/docs/latest/html/libraries/index.html
As for enforcing your particular invariants on the graph, you'll
probably want to create special functions for manipulating the graph
structure that ensure that these invariants are maintained -- use a
newtype or data declaration to create the data type they will act on,
and don't export the data constructors, only the functions used to
create structures of that type. This way, the user has no way to
create values of your type that are inconsistent with your invariants
(in this case, you want to enforce the constraint that each vertex has
at most one outward arc with a given label)
hope this helps
- Cale
On 22/12/05, Brian McQueen [EMAIL PROTECTED] wrote:
I'm curious what this user community would come up with in order to
implement the curious zigzag data structure. If you haven't heard
anything about it, its a simple but peculiar idea, by the guy who
dreamed up the Xanadu project: http://xanadu.com/zigzag/.
Conceptually it is cells with some sort of value, where each cell
has any number of connections to any other cell, but the connections
are conceptually labeled/grouped as though they were dimensions. So a
cell with the value Brian McQueen would have a link to dorky guy
in the Description dimension, and a link to 519 S. Frances in the
Street Address dimension. Obviously most people would have links in
those same dimensions passing through their own name's cell. My cell
might have a pointer to Hector in the Hero dimension while a
conceited man might have a link right back to itself in that same Hero
direction. So the structure is very flexible. There are interesting
examples on the web site of a Day Planner type of an app where each
day has a time line and each time has appointments and the
appointments have attendees and they all have personal contact
information ... But its all logically linked.
I imagine it would be something like this in C-like code:
struct cell { value; ptr_to_links };
struct link { { dimension; ptr_to_destination; ptr_to_link; };
struct dimension { name; id; } ;
As I write this I realise that I don't remember much, if any,
discussion in this group about data structures. I may be starting
with a non-functional way of thinking.
BTW I'm mostly still at the reading Haskell and fiddling with ghci phase.
Brian McQueen
___
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] zigzag data structure
Essentially, the structure that they define on that site is a graph with arcs labelled in such a way that any vertex has at most one outgoing arc with that label (and hence at most one incoming arc with that label as well). Sorry, I obviously didn't read that carefully enough, and both invariants need enforcing. That is, you have to ensure that there is at most one incoming arc with a given label as well. - Cale ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
