[Haskell-cafe] Functional programming for processing of large raster images
Recently Vo Minh Thu wondered if Haskell (or, I generalize, functional programming) can be of much use for computer graphics programming. I'd like to point out a project that experimentally shown that functional programming is of great help for processing of large raster images (24-bit PPM files). The paper describing the system has been accepted for `Science of Computer Programming' and is in press: Combining Partial Evaluation and Staged Interpretation in the Implementation of Domain-Specific Languages Christoph A. Herrmann, Tobias Langhammer The code for the system is available online http://infosun.fmi.uni-passau.de/cl/metaprog/imagefilter2-2005-10-30.tgz The previous [slightly obsolete] version of the paper, presented at the MetaOCaml'04 workshop, is available online http://www.fmi.uni-passau.de/forschung/mip-berichte/MIP-0410.html The paper includes a few pictures and the table with benchmark, so we can observe the benefits. Now, with offshoring and native MetaOCaml fully implemented, we can gain bigger benefits. In this project, functional programming does what it is probably best suited: to develop a `compiler' -- a compiler from a filter specification to quite efficient code. The code is specialized to all available static information. To be precise, the authors implement an interpreter -- which is then specialized to the source program and so interpretative overhead is removed and the code is optimized. Staging an interpreter automatically gives a compiler. Futamura projections are not only the fascinating, but useful, too. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] haskell companies
hello i wonder if there are companies that use haskell in practice. i'm a computer science student from switzerland (europe) and need to do an internship. since i find haskell very interesting i thought these two things could maybe be combined. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] haskell companies
On 6/21/06, Andreas Kägi [EMAIL PROTECTED] wrote: hello i wonder if there are companies that use haskell in practice. i'm a computer science student from switzerland (europe) and need to do an internship. since i find haskell very interesting i thought these two things could maybe be combined. I'd recommend trying to find a company that seems open to trying new ideas, and then use Haskell for whatever project you decide to do, if possible. So don't look specifically for a Haskell company look for any old project that suits your tastes and is with a company that won't demand that you use a particular language, and use Haskell for that. /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] haskell companies
Hi See section 7.1 in the latest HCAR at http://haskell.org/communities/11-2005/html/report.html Thanks Neil On 6/21/06, Andreas Kägi [EMAIL PROTECTED] wrote: hello i wonder if there are companies that use haskell in practice. i'm a computer science student from switzerland (europe) and need to do an internship. since i find haskell very interesting i thought these two things could maybe be combined. ___ 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: Functional programming for processing of large raster images
I think the issue wasn't using functional programming for large image processing, it was using Haskell. OCaml is notoriously fast and strict. Haskell/GHC is... lazy. Everyone knows that laziness is supposed to be a virtue. In practice, though, I'm one of the people who either can't wrap their heads around it or just find themselves having to fight it from the start. Should we all switch to OCaml? I wish I had a criteria to determine when to use Haskell and when to use OCaml. On Jun 21, 2006, at 8:15 AM, minh thu wrote: Thanks for pointing this out, although I knew that kind of answer via papers about Pan. It means I'll have to improve my compiler writing knowlegde :) mt 2006/6/21, [EMAIL PROTECTED] [EMAIL PROTECTED]: Recently Vo Minh Thu wondered if Haskell (or, I generalize, functional programming) can be of much use for computer graphics programming. I'd like to point out a project that experimentally shown that functional programming is of great help for processing of large raster images (24-bit PPM files). The paper describing the system has been accepted for `Science of Computer Programming' and is in press: -- http://wagerlabs.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Re: Functional programming for processing of large raster images
Hello Joel, Wednesday, June 21, 2006, 1:24:05 PM, you wrote: I think the issue wasn't using functional programming for large image processing, it was using Haskell. OCaml is notoriously fast and strict. Haskell/GHC is... lazy. +1 :) Everyone knows that laziness is supposed to be a virtue. In practice, though, I'm one of the people who either can't wrap their heads around it or just find themselves having to fight it from the start. i think that i just don't notice cases where i use lazy evaluation in Haskell, it just silently works. just for example - i have in my program filelist which can contain, say, 100.000 files. it is splitted to sublists by file extension and each sublist is splitted again to 100 items chunks. the each sub-sub-list is processed in inner cycle. that is done via lazy list evaluation and i even don't think how this actually works - for me it' just split+mapM_ combination Should we all switch to OCaml? I wish I had a criteria to determine when to use Haskell and when to use OCaml. i never tried to work in it but i've read books. for me it's just too irregular, uncomfortable language. from the theoretic point of view, Haskell has some stronger facilities (because it was created much later), such as polymorphic recursion and type classes. although OCaml is much later than original ML and contains numerous extensions, they are more pragmatic and not really integrated into the language (imho). Haskell, on the other side, grows with new high-level concepts that are moved from the academician fields right to the real work (say, STM and GADT) language-of-my-dream is strict Haskell with ability to explicitly specify lazy evaluation on need. it was discussed on this list several months ago (search for strict Haskell). one possibly interesting variant of these strict Haskell can be Clean language - it's also lazy by default, afaik, but contains better features to specify strictness, compiler that generates fast code (at the level of OCaml/jhc), plus IDE with GUI libs. comparing to Haskell, it seems somewhat like Visual Basic comparing to plain Basic. again, i don't tried it (and it's not free, afair), so look himself. it's a list of files i downloaded from site but not yet tried. first is compiler, other - docs (and it's a HUGE docs): HsCleanAll2.0.2.zip [http://aszt.inf.elte.hu/~fun_ver/2003/software/HsCleanAll2.0.2.zip] CleanBookI.pdf 1-up [ftp://ftp.cs.kun.nl/pub/Clean/papers/cleanbook/CleanBookI.pdf] CleanBookI2up.pdf 2-up [ftp://ftp.cs.kun.nl/pub/Clean/papers/cleanbook/CleanBookI2up.pdf] III.1.ProgramDevelopment.pdf pdf [ftp://ftp.cs.kun.nl/pub/Clean/papers/cleanbook/III.1.ProgramDevelopment.pdf] III.2.ProgStylesParadigms.pdf pdf [ftp://ftp.cs.kun.nl/pub/Clean/papers/cleanbook/III.2.ProgStylesParadigms.pdf] III.3.Efficiency.pdf pdf [ftp://ftp.cs.kun.nl/pub/Clean/papers/cleanbook/III.3.Efficiency.pdf] object-io.pdf [ftp://ftp.cs.kun.nl/pub/Clean/supported/ObjectIO.1.2/doc/tutorial.pdf] -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ... processing of large raster images : CLEAN
Bulat Ziganshin wrote: one possibly interesting variant of these strict Haskell can be Clean language - it's also lazy by default, afaik, but contains better features to specify strictness, compiler that generates fast code (at the level of OCaml/jhc), plus IDE with GUI libs. comparing to Haskell, it seems somewhat like Visual Basic comparing to plain Basic. again, i don't tried it (and it's not free, afair), so look himself. Yourself... ... You will find that Clean IS FREE under LGPL, although commercial versions exist as well. Don't spread dubious truths. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ... processing of large raster images : CLEAN
Hello Jerzy, Wednesday, June 21, 2006, 4:32:40 PM, you wrote: one possibly interesting variant of these strict Haskell can be Clean language - it's also lazy by default, afaik, but contains better features to specify strictness, compiler that generates fast code (at the level of OCaml/jhc), plus IDE with GUI libs. comparing to Haskell, it seems somewhat like Visual Basic comparing to plain Basic. again, i don't tried it (and it's not free, afair), so look yourself. ... You will find that Clean IS FREE under LGPL, although commercial versions exist as well. can you write more about Clean, about experience with it? i don't know exact LGPL rules - can it be used to develop commercial software and which parts (if any) is omitted in LGPL version? it will be very interesting to hear about Clean programming environment comparing with well-known RADs - .NET, Eclipse, Delphi? can you enlighten me? -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ghc-pkg on Windows XP
Hello, I have installed ghc-6.4.2 on a windows XP machine. However, the machine refuses to execute ghc-pkg (thus preventing me from using Cabal) and complains that C:\ghc\ghc-6.4.2\bin\ghc-pkg.exe is not a valid Win32 application. Is there something obvious I might have overlooked while installing? Also, I am new to using ghc on windows and was wondering what are the trade-offs of using cygwin or minsys versus just living in a emacs shell? thanks, Jeff -- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Simple matrix
I made a very simple matrix module that implements matrix sum and multiplication. It does not require any especific type since it uses Num [[a]]. So instead of typing something like Matrix [[1,0],[0,2]] * Matrix [[1,2],[3,4]] you can just type [[1,0],[0,2]]*[[1,2],[3,4]] It needs -fglasgow-exts Atila module SimpleMatrix where instance Num a = Num [[a]] where fromInteger x = [[fromInteger x]] abs x = map (map abs) x (+) [ ] y = y (+) x [ ] = x (+) x y = zipWith (zipWith (+)) x y (*) x y = map (matrixXvector x) y where --matrixXvector :: Num a = [[a]] - [a] - [[a]] matrixXvector m v = foldl vectorsum [] $ zipWith vectorXnumber m v --vectorXnumber :: Num a = [a] - a - [a] vectorXnumber v n = map (n*) v --vectorsum :: [a] - [a] - [a] vectorsum [] y = y vectorsum x [] = x vectorsum x y = zipWith (+) x y ___ Novidade no Yahoo! Mail: receba alertas de novas mensagens no seu celular. Registre seu aparelho agora! http://br.mobile.yahoo.com/mailalertas/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ... processing of large raster images : CLEAN
hi Bulat, shortly : with GPL you have to make your code GPL if it uses GPLed code. with LGPL you dont have to make your code LGPL/GPL if it only links against LGPLed library. regards, mt 2006/6/21, Bulat Ziganshin [EMAIL PROTECTED]: Hello Jerzy, Wednesday, June 21, 2006, 4:32:40 PM, you wrote: one possibly interesting variant of these strict Haskell can be Clean language - it's also lazy by default, afaik, but contains better features to specify strictness, compiler that generates fast code (at the level of OCaml/jhc), plus IDE with GUI libs. comparing to Haskell, it seems somewhat like Visual Basic comparing to plain Basic. again, i don't tried it (and it's not free, afair), so look yourself. ... You will find that Clean IS FREE under LGPL, although commercial versions exist as well. can you write more about Clean, about experience with it? i don't know exact LGPL rules - can it be used to develop commercial software and which parts (if any) is omitted in LGPL version? it will be very interesting to hear about Clean programming environment comparing with well-known RADs - .NET, Eclipse, Delphi? can you enlighten me? -- Best regards, Bulatmailto:[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] Simple matrix
fromInteger x = [[fromInteger x]] Wouldn't you want the expression [[1,0],[0,2]] + 10 to yield [[11,10],[10,12]] instead of [[11]] ? I guess you would need some complicated machinery so this is one thing you have to ignore to keep your otherwise nifty instance nice and simple. Jared. -- http://www.updike.org/~jared/ reverse )-: abs x = map (map abs) x (+) [ ] y = y (+) x [ ] = x (+) x y = zipWith (zipWith (+)) x y (*) x y = map (matrixXvector x) y where --matrixXvector :: Num a = [[a]] - [a] - [[a]] matrixXvector m v = foldl vectorsum [] $ zipWith vectorXnumber m v --vectorXnumber :: Num a = [a] - a - [a] vectorXnumber v n = map (n*) v --vectorsum :: [a] - [a] - [a] vectorsum [] y = y vectorsum x [] = x vectorsum x y = zipWith (+) x y ___ Novidade no Yahoo! Mail: receba alertas de novas mensagens no seu celular. Registre seu aparelho agora! http://br.mobile.yahoo.com/mailalertas/ ___ 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] Simple matrix
Sorry, a few corrections to my above points: On 21/06/06, David House [EMAIL PROTECTED] wrote: * Zipping the empty list with anything produces the empty list, so your two equations for (*) involving the empty list are redundant. I meant (+). * You define vectorsum, but don't seem to use it anywhere. Disregard this. -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc-pkg on Windows XP
Hello Jeff, Wednesday, June 21, 2006, 6:21:51 PM, you wrote: I have installed ghc-6.4.2 on a windows XP machine. However, the machine refuses to execute ghc-pkg (thus preventing me from using Cabal) and complains that C:\ghc\ghc-6.4.2\bin\ghc-pkg.exe is not a valid Win32 application. Is there something obvious I might have overlooked while installing? may be problems with memory, or broken download? i use cabal and ghc-pkg everyday, on the same platform (win xp and ghc 6.4.2). try to redownload/reinstall ghc. -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
Well, I was forcing A+[[]] to be A instead of [[]]. But who would do that kind of thing anyway? So I agree with you, those 2 (+) lines are useless. Atila David House wrote: Sorry, a few corrections to my above points: On 21/06/06, David House [EMAIL PROTECTED] wrote: * Zipping the empty list with anything produces the empty list, so your two equations for (*) involving the empty list are redundant. I meant (+). * You define vectorsum, but don't seem to use it anywhere. Disregard this. ___ Yahoo! doce lar. Faça do Yahoo! sua homepage. http://br.yahoo.com/homepageset.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional programming for processing of largeraster images
Joel Reymont wrote: I think the issue wasn't using functional programming for large image processing, it was using Haskell. OCaml is notoriously fast and strict. Haskell/GHC is... lazy. Everyone knows that laziness is supposed to be a virtue. In practice, though, I'm one of the people who either can't wrap their heads around it or just find themselves having to fight it from the start. Perhaps laziness is more foundational, in that you can write if2 c x y = if c then x else y However: 1) What's the advantage of being able to define if2? 2) Many control constructs, like =, foldl', map etc don't require laziness because they already take a function as argument rather than a plain expression. In fact, I can't think of any useful user defined control constructs that actually use laziness in the same way as if2, and the presence of laziness in foldr, foldl etc just seems to be a real pain leading to excessive heap consumption. (Counterexample? ) 3) Lazy lists as glue can easily be replaced by force/delay lists + an extension to pattern matching where pattern matching against [a] forces the argument and the syntax [h|t] is used as in Prolog, instead of h:t (This would also free : to be used for with type or with partial type instead of ::) 4) Other examples of the utility of laziness can turn out to be impractical chimera. For example, the famous repmin replaces the traversal of a tree twice with the dubious advantage of traversing it only once and the building up of a cluster of expensive thunks instead, and since the thunks effectively encode the structure of the tree, evaluation of them effectively constitutes the second traversal. So nothing's gained except difficulty of understanding the all-too-clever code (very bad software engineering practice imho), more heap consumption, and more time consumption. Should we all switch to OCaml? I wish I had a criteria to determine when to use Haskell and when to use OCaml. Everything else about Haskell is so great and well thought out (eg type classes, no side effects, higher rank polymorphism, existentials) it seems a pity to throw all this away just because of one unfortunate feature. An alternative would be to write a converter that reads a file of Haskell source which is to be interpreted strictly and outputs a file of lazy Haskell source with stictness annotations everywhere, with desugaring of [a] into force/delay representation (*). (Also in general, !x could mean force x ie x(), and ~x could mean \()-x (in value syntax) or ()-x (in type syntax), and !x could be allowed in patterns also (when the type at that position is ~x)) foo : ~Int - Int -- also taking the opportunity to replace :: by : foo !x = x desugared to foo :: (() - Int) - Int foo cx = case cx () of x - x The main challenge I think would be in converting bindings in let and where to appropriate case bindings to ensure that as far as possible, redundant bindings for a given path of control flow are not made, and analysis of mutually recursive bindings to ensure that everything is bound before being used. Some issues would need to be resolved about what the user can expect. For example whole program optimization could allow some expressions to be optimized out (eg by splitting a function returning a pair into two functions, one for each element) that would otherwise be non-terminating, whereas with lazy Haskell, there is an easy rule that (effectively) expressions are only evaluated when needed, regardless of optimization. Then an interesting investigation would be to see how easy it is to port lazy Haskell to the new, totally strict, language, and if there are any situations where existing code has used laziness (for algorithmic reasons or just for efficiency) without being aware of it. (*) So that eventually a new compiler could be written to take full advantage of the side-effect-free nature of the language + the strictness which means that values can be accessed without having to go through the if unevaluated then evaluate, store, and return else return for each unoptimized access. Because OCaml and SML have side effects, which limit optimizations due to possible aliasing etc, it might be possible to compile such a language to code which is certainly no slower, and possibly *even faster* than OCaml!!! :-) Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional programming for processing of largeraster images
Am Mittwoch 21 Juni 2006 21:30 schrieb Brian Hulley: Perhaps laziness is more foundational, in that you can write if2 c x y = if c then x else y However: 1) What's the advantage of being able to define if2? Well, you can easily define you own control structures (when, unless etc). This feature is wildly used in combinator libraries. Also, in a non-strict language recursive definitions are not limited to function types. Users of parser combinators heavily rely on this feature. Just try to define/use parsing combinators ins a strict language. The problem with eager evaluation is that it is too eager (expressions are sometimes evaluated too early) just as the problem with lazy evaluation is that it is too lazy (evaluations sometimes happen too late). Cheers, Ralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional programming for processing of largeraster images
Hi, I happen to like laziness, because it means that when I'm not thinking about performance, I don't have to think about evaluation order _at all_. And since my computer is a 750Mhz Athlon with Hugs, I never find any need to worry about performance :) If it ever becomes an issue I can move to GHC or buy a faster computer without too much hassle. 1) What's the advantage of being able to define if2? What about , || ? Should they be built in? What about and, which is just a lot of times, should that be lazy? At what point do you say no? Should I be able to define implies correctly? 3) Lazy lists as glue can easily be replaced by force/delay lists + an extension to pattern matching where pattern matching against [a] forces the argument and the syntax [h|t] is used as in Prolog, instead of h:t (This would also free : to be used for with type or with partial type instead of ::) That seems like more thought when writing the program, maybe its worth it, maybe its not, but it doesn't seem as neat as what we already have. 4) Other examples of the utility of laziness can turn out to be impractical chimera. For example, the famous repmin replaces the traversal of a tree twice with the dubious advantage of traversing it only once and the building up of a cluster of expensive thunks instead, and since the thunks effectively encode the structure of the tree, evaluation of them effectively constitutes the second traversal. So nothing's gained except difficulty of understanding the all-too-clever code (very bad software engineering practice imho), more heap consumption, and more time consumption. Laziness doesn't have to be exploited in complex ways - minimum = head . sort is a nice example. isSubstr x y = any (isPrefix x) (inits y) is another one. Often by just stating a definition, laziness gives you the performance for free. Of course, if you wanted to think harder (and I never do), you can write better performing and strict-safe versions of these, but again its more effort. The other thing you loose when moving to strictness is the ability to inline functions arbitrarily - consider: if2 c t f = if x then t else f Consider the expression: if2 True 1 undefined Now lets inline it and expand it, and in Haskell we get 1, which matches the evaluation. In strict Haskell the inlining is now invalid, and thats quite a useful optimisation to make. While it seems that compilers can get round this, my concern is for the poor programmer - this nice property of viewing functions as just replace this with that has disappeared. I suspect that in years to come, lazy languages will also have the upper hand when it comes to theorem proving and formal reasoning, but I guess thats a matter for future consideration. While laziness may not be all good, its certainly not all bad :) Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional programming for processing of largeraster images
On Jun 21, 2006, at 3:30 PM, Brian Hulley wrote: Joel Reymont wrote: I think the issue wasn't using functional programming for large image processing, it was using Haskell. OCaml is notoriously fast and strict. Haskell/GHC is... lazy. Everyone knows that laziness is supposed to be a virtue. In practice, though, I'm one of the people who either can't wrap their heads around it or just find themselves having to fight it from the start. Perhaps laziness is more foundational, in that you can write if2 c x y = if c then x else y [snip some conversation...] For those who haven't seen this already, here is a presentation by Simon PJ in which he discusses his views on laziness (among other things). http://research.microsoft.com/~simonpj/papers/haskell-retrospective/ HaskellRetrospective.pdf Takeaway point about laziness: Laziness keeps you honest by not allowing you to slip in side effects. Bonus takeaway: read Wadler's papers :-) Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Template haskell and scoping
The (..) in the splice is out of scope according to GHC. If I use [||] then it works, but for my purposes it's easier to use the constructors. How should I refer to that variable? import Data.Bits import Language.Haskell.TH main = print $ $(return $ VarE $ mkName ..) 7 (14 :: Int) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
Jared Updike wrote: Wouldn't you want the expression [[1,0],[0,2]] + 10 to yield [[11,10],[10,12]] You could handle this as a special case in (+) and (*), but this is kind of a hack. Something like: (+) [[x]] y = map (map (x+)) y (+) x [[y]] = map (map (+y)) x (+) xy = zipWith (zipWith (+)) x y Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
I dont see how to fix this. There was a thread about statically knowing lots about the shape of matrices using the type system. http://www.haskell.org/pipermail/haskell/2006-April/017845.html I believe they incorporated this (variable size identity matrix, for example) in their approach. (They don't preserve your property of being able to do things with simple list syntax, like [[1,2],[3,4]] * [[5,6],[7,8]] , instead you have to use Template Haskell and some small contructor functions) Could be better to forget about fromInteger... Except then you wouldn't have a full instance for Num. How about constructing an infite list of infinite lists of that number: fromInteger x = map repeat (repeat (fromInteger x)) when it gets zipped with smaller matrices, will it terminate? It works with addition but multiplying caused problems: [[1,2],[3,4]] + 10 = [[11,12],[13,14]] [[1,2],[3,4]] * 10 = [[40,60],[40,60],[40,60],[40,60],[40,60], . Hmm... Jared. Atila Jared Updike wrote: fromInteger x = [[fromInteger x]] Wouldn't you want the expression [[1,0],[0,2]] + 10 to yield [[11,10],[10,12]] instead of [[11]] ? I guess you would need some complicated machinery so this is one thing you have to ignore to keep your otherwise nifty instance nice and simple. Jared. -- http://www.updike.org/~jared/ reverse )-: ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
Here is one way to do it. First, you have to interpret operations on matrices as being elementwise applied. E.g, (*) is interpreted as zipWith (zipWith (*)) rather than matrix multiply, and similar for (+) etc. You then obtain a lazy semantics for the operations, where the extent of the resulting matrix is the intersection of the extents of the argument matrices. Second, you lift constants into infinite matrices containing the constant, that is: fromInteger n = repeat (repeat n). Now your examples will work as intended. Björn Lisper Atila Romero: Good point. And there is another problem: one could expect 10 * [[1,2],[3,4]] to be equal to [[10,20],[30,40]] and in this case 10 should be equal to [[10,0],[0,10]], instead of [[10,10],[10,10]] or [[10]]. I dont see how to fix this. Could be better to forget about fromInteger... Atila Jared Updike wrote: fromInteger x = [[fromInteger x]] Wouldn't you want the expression [[1,0],[0,2]] + 10 to yield [[11,10],[10,12]] instead of [[11]] ? I guess you would need some complicated machinery so this is one thing you have to ignore to keep your otherwise nifty instance nice and simple. Jared. ___ Novidade no Yahoo! Mail: receba alertas de novas mensagens no seu celular. Registre seu aparelho agora! http://br.mobile.yahoo.com/mailalertas/ ___ 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] Simple matrix
Instead of fromInteger x = map repeat (repeat (fromInteger x)) I meant fromInteger x = repeat (repeat (fromInteger x)) but it still doesn't work for multiplication. Jared. -- http://www.updike.org/~jared/ reverse )-: ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Functional _meta_programming for processing of large raster images
I'm afraid the _meta_ programming aspect of the image processing project may be overlooked. Joel Reymont wrote: I think the issue wasn't using functional programming for large image processing, it was using Haskell. OCaml is notoriously fast and strict. Haskell/GHC is... lazy. Well, in the raster image processing project, a dialect of OCaml was used to _generate_ code. If the author used offshoring (which I think they did later), the generated code was in C. That C code can be used stand-alone or be linked with some other C (Java, etc) code. Our FFT paper did exactly that: our MetaOCaml program produced C code, which we plugged as it was in the FFTW testing framework (written in pure C) for benchmarking. By 'plugged' above I meant moving the C code file from one directory to another. We used both GCC and Intel C compilers for benchmarking. Offshoring can also produce Fortran code. It's quite feasible to generate Verilog so we can program an FPGA and get image processing even faster. The generator doesn't have to be a speed demon; it is not that relevant if the generator is lazy or strict. What really matters if the generator can be easily judged correct. It immensely matters that the generated code has correctness properties; at least, it should be well-formed and well-typed (and preferably, has some other properties, like space bounds). It is disheartening to see errors when compiling the generated code (as happens with some other generators), because it is very difficult to trace these errors back to the generator. Here's the reference to another, quite large and very real project http://www.spiral.net/ which generates the fastest ever FFT, DCT, etc. codes for variety of architectures. The source language is a DSL for linear algebra. The point is that highest-performance computing nowadays is all about code generation/meta-programming. And in this area, functional programming and Haskell have definite advantage. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Functional progr., images, laziness and all the rest
Usually once a year somebody starts a discussion on the merits of functional/lazy paradigms, etc., in an applicative context, and it is quite good. People compare Haskell and Ocaml, from time to time somebody says that - apparently - Clean has better handling of strictness issues [saying at the same time that he/she doesn't use Clean...], people divide into different philosophical branches, some complain that it would be nice to have strict Haskell, others say, that they don't care, and what is important is the provable/enforced correctness, and laziness is helpful. People say that the laziness permits to consider the conditionals as functions, others ask what for, and the discussion is usually quite interesting. And here apparently I am one of rare people - I am not proud of it, rather quite sad, who defends laziness as an *algorithmisation tool*, which makes it easy and elegant to construct co-recursive codes. Circular programs, run-away infinite streams, hidden backtracking etc. In the domain of images this can be helpful for making filters, especially infinite-response, recursive filters. For two-dimensional data this might be clumsy, but for 1D, for example for the sound generation/processing, you may transform a recurrential equation yielding Y out of X: Y[n+1] = a*X[N+1] + b*Y[n] usually (imperatively) implemented as a loop, into a stream definition: filtr a b x@(x0:xq) = y where y = (x0:yq) yq = a*xq + b*y with (*) and (+) conveniently overloaded (or replaced by specific obvious ops). In such a way you can program in 2 - 6 lines some quite exquisite musical instruments (for example the Karplus-Strong guitar, or a flute), construct the reverberation filters, make ever-rising Shepard/Risset paradoxical sounds, etc. etc. With laziness it is a sheer pleasure and fun, without - a pain. If you wish, find my PADL talk on it... In this context, I found Clean more helpful than Haskell, for ONE reason. Clean has a primitive datatype: unboxed, spine-lazy but head-strict lists. The co-recursion works, as the construction of the tail is postponed, but there is no pollution of the space by thunks - unevaluated list *elements*. This I really do miss in Haskell... But perhaps I simply don't know how to obtain a similar behaviour? For image processing (rather: constructing, but with incremental algorithms) Clean usage of unique arrays was for me more natural than monadic stuff in Haskell, but this is probably just a question of style. I agree that here the laziness is secondary... Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Functional progr., images, laziness and all the rest
[EMAIL PROTECTED] wrote: [snip] you may transform a recurrential equation yielding Y out of X: Y[n+1] = a*X[N+1] + b*Y[n] usually (imperatively) implemented as a loop, into a stream definition: filtr a b x@(x0:xq) = y where y = (x0:yq) yq = a*xq + b*y Can you explain how this transformation was accomplished? I don't see how yq = a * xq + b * y relates to Y[n+1] = a*X[n+1] + b*Y[n] -- (assuming the X[N+1] was a typo) since y is a longer list than yq but Y[n] is an earlier element than Y[n+1], so it seems that the function is multiplying b by a later factor than it should. So: 1) Someone reading the code needs to do a lot of work to try to recover the original equation 2) Wouldn't an imperative loop, using the original equation directly, have made everything much simpler? 3) Therefore laziness has lead to obfuscated code. with (*) and (+) conveniently overloaded (or replaced by specific obvious ops). In such a way you can program in 2 - 6 lines some quite exquisite musical instruments (for example the Karplus-Strong guitar, or a flute), construct the reverberation filters, make ever-rising Shepard/Risset paradoxical sounds, etc. etc. With laziness it is a sheer pleasure and fun, without - a pain. If you wish, find my PADL talk on it... In this context, I found Clean more helpful than Haskell, for ONE reason. Clean has a primitive datatype: unboxed, spine-lazy but head-strict lists. The co-recursion works, as the construction of the tail is postponed, but there is no pollution of the space by thunks - unevaluated list *elements*. This I really do miss in Haskell... But perhaps I simply don't know how to obtain a similar behaviour? If you only needed the head-strict aspect, something like data HSList a = Empty | Cons !a (HSList a) (GHC also has unboxed types so perhaps something like data HSList = Empty | Cons Double# HSList but see the restrictions on their use at http://www.haskell.org/ghc/docs/latest/html/users_guide/primitives.html ) Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
