Re: [Haskell-cafe] Grouping and SIMD in parallel Haskell (using Nested Data Parallel Haskell ideas in legacy code)
Now I finally understood the idea that you were talking about :) I didn't quite get it during the MskHUG meeting. The idea is brilliant to my mind; I am surprised that none of the gurus are answering. So, if I understood it correctly, you are suggesting to: - make a separate spark queue (implemented by a linked list of groupSize-sized arrays) for every thunk type in the program that can possibly be the argument of a `par` or `pseq` (which, however, may turn out to be almost all thunk types present in the program) - automagically create vectorized versions of these thunks' code - spawn sparks by appending them to the corresponding queue (to a non-locked array node?) - evaluate sparks in a vectorized fashion by invoking the vectorized code over groups The problems I see here are: - not all thunks code can be vectorized automatically - how should we represent the sparks in the queue for a certain thunk type? It's clear that it is no longer needed to put the whole closure into the spark queue, since the closure code is already known and fixed for each queue. For efficient vectorization, the queue probably should consist of closure data arrays. - I do not immediately see an efficient (lockless) way of picking a nonempty spark queue; however, I am sure there must be such a way, and even if there isn't, the inefficiency may well be overweighted by the efficiency gain from vectorization 2009/8/17 Zefirov Sergey zefi...@prosoft.ru: I haven't had enough time to polish a paper about the subject, so I decided to post my results here, in Haskell Café. When Simon Peyton-Jones was in Moscow about a month ago I made a bold statement that Parallel Haskell programs, expressed with the help of par and pseq, can be transformed into Nested Data Parallel Haskell. I wrote a simple model of what will be if we group arguments of par and pseq into queues based on parallel arrays from NDPH. We could then evaluate all thunks from that queues in parallel using SIMD (or just getting higher ILP). We also do not have to lock out main spark queue, we lock only queue we should put argument in. The latter turned out to be beneficial in itself, at least in my simple model. Let us look at famous parallel fib function: Fib n | N = 1 = 1 | otherwise = a `par` b `pseq` a+b where a = fib (n-1) b = fib (n-2) When we evaluate fib we put a spark of a into spark queue and proceed to evaluate b and, then, a+b. When we put a into spark queue, we lock queue out, modify and release. There is a big probability that threads on different cores will compete for queue lock and some of them (most of them) will waste time waiting for lock release. If we group a's into different queue and put to main spark queue a spark to evaluate a complete group of a's at once, we will get less wasted time. This will work even for single CPU. Below is a run of (fib 15) on my model with cpuCount 1, 4 and 16 and a's or b's group length 0 (no grouping) and 16: cpuCount groupLength=0 groupLength=16 modelTicks modelTicks 1 34535 27189 4 12178 7472 16 7568 3157 speedup 2.19 times 3.11 times ticks1/ticks16 I think results speak for itself. I think the idea of `par` argument grouping could be viable. I should note that I made several digressions when I wrote model. One of digressions is that all evaluations are put into queue. In (a `par` b `pseq` a+b) a put into a_queue, b put into b_queue and (a+b) put into main queue. Each evaluated spark update it's parent - a spark that wait for it. Also, main loop of single CPU changed from simple (reading main spark queue + execute when get something) into a series of attepmts with fall back on failure: - first read main queue and execute spark if succeed, - else read current a_queue and execute all sparks there if succeed, - else read current b_queue and execute all sparks there if succeed, - else go to main loop. The new (transformed) code for our fib below: -- |Create a new queue based on parallel array. It holds a parallel array with current arguments and a function that performs -- computation in RTS monad (evaluation function). newQueueParArray :: (x - RTS ()) - RTSRef ([: x :],x - RTS ()) a_queue = unsafePerformIO $ newQueueParArray (\x - fib (x-1)) -- RTSRef (Int,Int - Int) b_queue = unsafePerformIO $ newQueueParArray (\x - fib (x-2)) -- RTSRef (Int,Int - Int) fib n caller | n = 1 = 1 | otherwise = unsafePerformIO $ do Ab - addToMainQueue (defer (+) caller) A' - addToParArrQueue a_queue x ab B' - addToParArrQueue b_queue x ab addToMainQueue ab -- add a spark to check a' and b' evaluation status, compute a+b and update the caller. That transfomation cannot be done at the source level using usual type
[Haskell-cafe] REMINDER: Next BostonHaskell meeting TOMORROW (August 18th) at MIT
The full details of the event are here: http://groups.google.com/group/bostonhaskell/browse_thread/thread/71243e7d2ec57300 I'm just sending out this reminder to make sure more people hear about the event (especially as, with Brent on vacation, there wasn't a Haskell Weekly News this week). If you're planning to come please respond to our scheduling poll at: http://doodle.com/participation.html?pollId=x8rbbbprtezdtaan This will help us get a better count of attendees for refreshments (since my wife has volunteered to make more baked goodies). Please also respond to the poll if you're interested in BostonHaskell, but couldn't come this month because of scheduling or location constraints. That will help us improve planning for future meetings. I look forward to seeing many Boston-area Haskellers tomorrow! Thanks, - Ravi Nanavati ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Can't install Haskell Platform on 64-bit Linux
I installed GHC 6.10.4 (as ./configure said it was required) from a .bz2 file on the GHC downloads page. I then tried ./configure for the platform again, and got: checking ghc actually works... no configure: error: Your installation of ghc does not appear to work. It cannot compile a simple program (see config.log for the details). If you installed ghc from a generic binary tarball then it is worth checking that you have the 'gmp' C library and header files installed. (On debian-based systems this package is called libgmp3-dev.) Looking in config.log, I see: configure:2287: checking ghc actually works configure:2296: /usr/local/bin/ghc -o conftest conftest.hs /tmp/ghc22651_0/ghc22651_0.s: Assembler messages: /tmp/ghc22651_0/ghc22651_0.s:43:0: Error: suffix or operands invalid for `push' /tmp/ghc22651_0/ghc22651_0.s:89:0: Error: suffix or operands invalid for `push' /tmp/ghc22651_0/ghc22651_0.s:135:0: Error: suffix or operands invalid for `push' configure:2299: $? = 1 configure: failed program was: main = putStr Hello world!\n -- this file generated by TRY-COMPILE-GHC end of failed program. configure:2308: result: no configure:2314: error: Your installation of ghc does not appear to work. It cannot compile a simple program (see config.log for the details). If you installed ghc from a generic binary tarball then it is worth checking that you have the 'gmp' C library and header files installed. (On debian-based systems this package is called libgmp3-dev.) Libgmp is installed. I don't know the significance of the assembler error messages. If I type from the command line: ghci I get the Prelude prompt, so it looks like the installation is OK at first glance. What should I check next? -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can't install Haskell Platform on 64-bit Linux
On Tue, Aug 18, 2009 at 10:25 AM, Colin Paul Adamsco...@colina.demon.co.uk wrote: I installed GHC 6.10.4 (as ./configure said it was required) from a .bz2 file on the GHC downloads page. I then tried ./configure for the platform again, and got: What distribution of Linux do you use? I'd strongly suggest getting it from your distro's repo rather than downloading the tar-ball. That way you avoid satisfying dependencies manually. /M -- Magnus Therning(OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can't install Haskell Platform on 64-bit Linux
Magnus == Magnus Therning mag...@therning.org writes: Magnus On Tue, Aug 18, 2009 at 10:25 AM, Colin Paul Magnus Adamsco...@colina.demon.co.uk wrote: I installed GHC 6.10.4 (as ./configure said it was required) from a .bz2 file on the GHC downloads page. I then tried ./configure for the platform again, and got: Magnus What distribution of Linux do you use? Fedora. Magnus I'd strongly suggest getting it from your distro's repo Magnus rather than downloading the tar-ball. That way you avoid Magnus satisfying dependencies manually. It's not available. -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Grouping and SIMD in parallel Haskell (using Nested Data Parallel Haskell ideas in legacy code)
-Original Message- From: Eugene Kirpichov [mailto:ekirpic...@gmail.com] Sent: Tuesday, August 18, 2009 11:28 AM To: Zefirov Sergey Cc: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Grouping and SIMD in parallel Haskell (using Nested Data Parallel Haskell ideas in legacy code) Now I finally understood the idea that you were talking about :) I didn't quite get it during the MskHUG meeting. The idea is brilliant to my mind; I am surprised that none of the gurus are answering. So, if I understood it correctly, you are suggesting to: - make a separate spark queue (implemented by a linked list of groupSize-sized arrays) for every thunk type in the program that can possibly be the argument of a `par` or `pseq` (which, however, may turn out to be almost all thunk types present in the program) Yep. And it could be beneficiary by itself. - automagically create vectorized versions of these thunks' code If we can. Looks like we can. ;) - spawn sparks by appending them to the corresponding queue (to a non-locked array node?) Sparks queues can be non-locked if they belong to threads. Or, in other words, each thread has it's own spark's queue and all threads share main queue. If sparks queues are shared between threads, they should be locked. My model suggests that private spark queues slows down execution speed, but I haven't paid enough attention to the subject so my code could be wrong. Look yourself: usePrivateGroups maxABTaskLength ticks (fib 15) 0 07568 0 16 3157 0 32 2977 1 07753 1 16 3772 1 32 4242 All other parameters are: cpuCount 16 taskFetchsPerCycle 1 thunksPerAddition 1 cyclesPerAddition 1. Anyway, let's say we have several processors and they all share all queues. When one processor encounter that some queue is locked it immediately proceed to another queue, which could be locked with less probability. - evaluate sparks in a vectorized fashion by invoking the vectorized code over groups Again, if we can. The problems I see here are: - not all thunks code can be vectorized automatically I tried to find a contradictory example and failed. But I haven't tried very hard. ;) I noticed that first argument for par should be considered strict. So we can demand that fib will receive Int# instead of boxed (and delayed) Int. Operations on [:Int#:] ([:Float#:], [:Char#:]) should be very efficient. An argument could be delayed (lazy) or of an algebraic type (like Maybe). Here we will have forcing of computation or pattern matching and, therefore, conditional execution. Conditional execution could be expressed in parallel SIMD operations, an example is given at Tim Sweeney presentation (near the end). (http://graphics.cs.williams.edu/archive/SweeneyHPG2009/TimHPG2009.pdf) The version there isn't best possible, but it works. - how should we represent the sparks in the queue for a certain thunk type? It's clear that it is no longer needed to put the whole closure into the spark queue, since the closure code is already known and fixed for each queue. For efficient vectorization, the queue probably should consist of closure data arrays. I think we would borrow closure representation from NDP Haskell. ;) - I do not immediately see an efficient (lockless) way of picking a nonempty spark queue; however, I am sure there must be such a way, and even if there isn't, the inefficiency may well be overweighted by the efficiency gain from vectorization With different sparks queues we prevent frequent locking of main spark queue. CPUs get more work per single lock. I think it's good in itself, vectorization could only add to it. Look at the table: maxABTaskLength ticks (fib 15) 07568 15651 24656 43663 83263 16 3157 32 2977 64 2931 (other model parameters: cpuCount 16 usePrivateGroups 0 maxABTaskLength variable taskFetchsPerCycle 1 thunksPerAddition 1 cyclesPerAddition 1) The effect on vectorization according to my model is negligible: thunksPerAddition 2 results in 2894 ticks and then time stop lowering. Increase in taskFetchsPerCycle also does not provide any noticeable speed up. I cannot promise because, but I will try to implement my idea because I already see it as a good idea. ;) PS I always fascinated how Haskell is amenable for RTS changes. Add a complication underneath once and free yourself from complication on the surface for ever. ;) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Library function for map+append
Hello all, During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap I tried hoogle to find such a function with no success. Is there any function/functions built-in standard libraries that could easily satisfy the functionality with the same or even better (?) efficiency? Of course, (map f list) ++ append would do the same as mapapp f list append but with less efficiency. Or am I wrong? Thanks Dusan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
Hi. Have you done any measurements that prove that such a function would indeed increase performance noticeably? 2009/8/18 Dusan Kolar ko...@fit.vutbr.cz: Hello all, During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap I tried hoogle to find such a function with no success. Is there any function/functions built-in standard libraries that could easily satisfy the functionality with the same or even better (?) efficiency? Of course, (map f list) ++ append would do the same as mapapp f list append but with less efficiency. Or am I wrong? Thanks Dusan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Library function for map+append
From: haskell-cafe-boun...@haskell.org [mailto:haskell-cafe-boun...@haskell.org] On Behalf Of Dusan Kolar During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap I tried hoogle to find such a function with no success. Is there any function/functions built-in standard libraries that could easily satisfy the functionality with the same or even better (?) efficiency? What does mapapp do? What is its type? At first I thought maybe you were rewriting concatMap, but now I can't tell what you're doing. http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.htm l#v%3AconcatMap Alistair * 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
Re: [Haskell-cafe] Library function for map+append
Dusan Kolar wrote: Hello all, During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap I tried hoogle to find such a function with no success. Is there any function/functions built-in standard libraries that could easily satisfy the functionality with the same or even better (?) efficiency? Of course, (map f list) ++ append would do the same as mapapp f list append but with less efficiency. Or am I wrong? Thanks Dusan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe mapapp = ((++) .) . map Reasoning about efficiency in a pure lazy language is different. -- Tony Morris http://tmorris.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
Hello Dusan, Tuesday, August 18, 2009, 2:50:38 PM, you wrote: but with less efficiency. Or am I wrong? probably wrong. haskell is lazy language also there is differential lists (dlist) implementation on hackage -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Library function for map+append
mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap What does mapapp do? What is its type? Never mind, I've got it now. Alistair * 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
Re: [Haskell-cafe] Library function for map+append
Dlists maybe good it all the app is written using them. Probably not good idea to switch to them in the middle of project... I know it is lazy, but I don't think it is able to eliminate operations, is it? At least intuitively, the map f list takes n*C ticks (C is for application of f and list creation, n is the list length, f is of no importance, it is always the same, but list probably must be created due to ++). Then, (++) take n*K ticks (K for list creation - I want to write out the list at the end, so that it is created). In my case (mapapp), it is n*CK, where CK stands for f and list creation... the CK is very similar to C... Thus, I should save the n*K, or at least its large portion... shouldn't I? If not, how the compiler can eliminate the operations? Dusan Bulat Ziganshin wrote: Hello Dusan, Tuesday, August 18, 2009, 2:50:38 PM, you wrote: but with less efficiency. Or am I wrong? probably wrong. haskell is lazy language also there is differential lists (dlist) implementation on hackage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
2009/8/18 Dusan Kolar ko...@fit.vutbr.cz: Hello all, During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap I tried hoogle to find such a function with no success. Is there any function/functions built-in standard libraries that could easily satisfy the functionality with the same or even better (?) efficiency? Can't think of something like that either but at least we can make it shorter and less readable ;) mapapp f xs tail = foldr ((:) . f) tail xs Of course, (map f list) ++ append would do the same as mapapp f list append but with less efficiency. Or am I wrong? Yes, that is less efficient because ++ has to create N new cons cells if list has length N. -- Fruhwirth Clemens http://clemens.endorphin.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] simulation in the haskell way
Hello, Haskellers! I'm relatively new to haskell and due to my strong imperative background, it's really a pain to learn haskell. But I'm really indulged in it. :) Now I think I understand the basics of Haskell very well, such as the type system and monad. And for those data-flow kind of applications, I can easily structure the problem in a functional way and sketch out an intuitive picture of the computation. But for simulation kind-of problems, in which I think OO really fits the best, what's the haskell way to structure such problems? I once thought maybe I can use the State monad to simulate objects. But it's really hard for me to implement, because I think State monad is used to simulate a global shared state, is it right? Then what's the best way to simulate private states or just instead how to solve simulation problems such as a physical engine using the haskell way? Best regards. Eric ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
Dusan Kolar ko...@fit.vutbr.cz writes: Dlists maybe good it all the app is written using them. Probably not good idea to switch to them in the middle of project... I know it is lazy, but I don't think it is able to eliminate operations, is it? At least intuitively, the map f list takes n*C ticks (C is for application of f and list creation, n is the list length, f is of no importance, it is always the same, but list probably must be created due to ++). Then, (++) take n*K ticks (K for list creation - I want to write out the list at the end, so that it is created). In my case (mapapp), it is n*CK, where CK stands for f and list creation... the CK is very similar to C... Thus, I should save the n*K, or at least its large portion... shouldn't I? If not, how the compiler can eliminate the operations? IMHO, the best way to reason about functional programs is via equational reasoning. So let's consider straightforward definitions for map and (++): map f [] = [] map f (x:xs) = f x : map f xs (++) [] l = l (++) (x:xs) l = x : (xs ++ l) Now let's see what happens with (map f x) ++ y doing case analysis and simplification with the above equations: (map f []) ++ y = [] ++ y = y (map f (x:xs)) ++ y = (f x : map f xs) ++ y = f x : (map f xs ++ y) So: (map f []) ++ y = y (map f (x : xs)) ++ y = f x : (map f xs ++ y) Now consider trivial definition for mapapp: mapapp f x y = (map f x) ++ y. Substituting this backwards into the above equations, we get: mapapp f [] y = y mapapp f (x : xs) y = f x : (mapapp f x xs) which is exactly the definition you've listed. Of course, a Haskell implementation is not *required* to do such transformations, but unless you really observe the difference in performance, it's more or less safe to assume there would be no intermediate list creation/destruction. -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
Clemens Fruhwirth clem...@endorphin.org writes: 2009/8/18 Dusan Kolar ko...@fit.vutbr.cz: Hello all, During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap I tried hoogle to find such a function with no success. Is there any function/functions built-in standard libraries that could easily satisfy the functionality with the same or even better (?) efficiency? Can't think of something like that either but at least we can make it shorter and less readable ;) mapapp f xs tail = foldr ((:) . f) tail xs Of course, (map f list) ++ append would do the same as mapapp f list append but with less efficiency. Or am I wrong? Yes, that is less efficient because ++ has to create N new cons cells if list has length N. No, it does not *have to*. Fruhwirth Clemens http://clemens.endorphin.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can't install Haskell Platform on 64-bit Linux
Magnus == Magnus Therning mag...@therning.org writes: Magnus Ouch, there only seems to be a version of 6.10.3 in Fedora Magnus 11, if I read this correctly: Magnus https://admin.fedoraproject.org/pkgdb/packages/name/ghc Magnus (I'm not a Fedora user so I might be completely confused Magnus here :-) Magnus It looks like the pre-built ghc can't find the installed Magnus libgmp. I don't think it's a problem with libgmp. I think that's just a cautionary message, based on experience that this is a common error. -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
module Main where mymap f xs = m xs where m [] = [] m (x:xs) = f x:m xs mymapp1 f xs ys = m xs where m [] = ys m (x:xs) = f x:m xs mymapp2 f [] ys = ys mymapp2 f (x:xs) ys = f x:mymapp2 f xs ys mapp1 f xs ys = (f`map`xs) ++ ys mapp2 f xs ys = (f`mymap`xs) ++ ys mapp3 f xs ys = mymapp1 f xs ys mapp4 f xs ys = mymapp2 f xs ys mapp = mapp1 main = putStrLn . show . length $ mapp (+1) [1..1] [1,2,3] mapp1: 3.764s mapp2: 5.753s mapp3: 4.302s mapp4: 4.767s So, the fastest way is the simplest one. 18 августа 2009 г. 17:12 пользователь Artem V. Andreev (ar...@aa5779.spb.edu) написал: Clemens Fruhwirth clem...@endorphin.org writes: 2009/8/18 Dusan Kolar ko...@fit.vutbr.cz: Hello all, During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap I tried hoogle to find such a function with no success. Is there any function/functions built-in standard libraries that could easily satisfy the functionality with the same or even better (?) efficiency? Can't think of something like that either but at least we can make it shorter and less readable ;) mapapp f xs tail = foldr ((:) . f) tail xs Of course, (map f list) ++ append would do the same as mapapp f list append but with less efficiency. Or am I wrong? Yes, that is less efficient because ++ has to create N new cons cells if list has length N. No, it does not *have to*. Fruhwirth Clemens http://clemens.endorphin.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- S. Y. A(R). A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: simulation in the haskell way
Eric Wong wsy...@gmail.com wrote: I'm relatively new to haskell and due to my strong imperative background, it's really a pain to learn haskell. But I'm really indulged in it. :) Now I think I understand the basics of Haskell very well, such as the type system and monad. And for those data-flow kind of applications, I can easily structure the problem in a functional way and sketch out an intuitive picture of the computation. But for simulation kind-of problems, in which I think OO really fits the best, what's the haskell way to structure such problems? I once thought maybe I can use the State monad to simulate objects. But it's really hard for me to implement, because I think State monad is used to simulate a global shared state, is it right? Then what's the best way to simulate private states or just instead how to solve simulation problems such as a physical engine using the haskell way? A state monad is used to encode a stateful computation. Whether its state is global or not really only depends on how long the computation lives. Here is how you can use one to maintain a list of objects: computation :: State [Object] Result computation = do objs0 - get (result, objs1) - doSomethingWith objs0 put objs1 return result This is really just a convenient encoding of: computation :: [Object] - (Result, [Object]) Whether that [Object] state is global really only depends on where you use evalState, execState or runState and how long the computation takes. I often do something like this, which you can regard as global 'state' (or rather a global environment): type AppIO = ReaderT AppConfig IO myApp :: AppIO () myApp = ... main :: IO () main = getAppConfig = evalStateT myApp Greets, Ertugrul. -- nightmare = unsafePerformIO (getWrongWife = sex) http://blog.ertes.de/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: simulation in the haskell way
Ertugrul Soeylemez e...@ertes.de wrote: computation :: State [Object] Result computation = do objs0 - get (result, objs1) - doSomethingWith objs0 put objs1 return result Misindented, sorry. Again: computation :: State [Object] Result computation = do objs0 - get (result, objs1) - doSomethingWith objs0 put objs1 return result Greets, Ertugrul. -- nightmare = unsafePerformIO (getWrongWife = sex) http://blog.ertes.de/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Looking up functions inQ monad (Template Haskell).
Why isn't possible to lookup and call user-defined functions while performing Template Haskell actions? Just like the way Template Haskell looks up and calls 'f' in $(f ...). 'f' gets looked up and called. And user of Q monad cannot do that. A colleague of mine, a Lisp user, says that almost everything is in place. It's just not enabled. Is there any problem we do not understand? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] simulation in the haskell way
You need to look into functional reactive programming, but be warned, this is active research :-) Two libraries I know of in which you can currently make working simulations are Yampa and Elerea. But the former doesn't scale really well, and the latter might not really be functional (I think it's not referentially transparent) Other libraries such as Reactive and Grapefruit are very promising, but I don't know their current status. Good luck. For me (I'm also an experienced imperative programmer in the simulation field), Haskell is very addictive, but also insanely frustrating because I never have the feeling I know the language well enough and I don't see the big picture yet. So I can't yet achieve in Haskell what I can in other languages, but purity and laziness are drugs, so you're doomed :-) On Tue, Aug 18, 2009 at 2:42 PM, Eric Wong wsy...@gmail.com wrote: Hello, Haskellers! I'm relatively new to haskell and due to my strong imperative background, it's really a pain to learn haskell. But I'm really indulged in it. :) Now I think I understand the basics of Haskell very well, such as the type system and monad. And for those data-flow kind of applications, I can easily structure the problem in a functional way and sketch out an intuitive picture of the computation. But for simulation kind-of problems, in which I think OO really fits the best, what's the haskell way to structure such problems? I once thought maybe I can use the State monad to simulate objects. But it's really hard for me to implement, because I think State monad is used to simulate a global shared state, is it right? Then what's the best way to simulate private states or just instead how to solve simulation problems such as a physical engine using the haskell way? Best regards. Eric ___ 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
[Haskell-cafe] Re: ANN: OpenCLRaw 1.0.1000
There was a missing include in the cabal file. fixed... On Mon, Aug 17, 2009 at 7:49 PM, Jeff Heardjefferson.r.he...@gmail.com wrote: All, I've released a raw binding to the OpenCL platform on Hackage. The main differences between it and the C bindings are that constants have been replaced by newtypes for type safety reasons, void-essential functions that return a token errorcode return a Maybe ErrorCode, and functions that return a handle/ptr and return an error-code through an out-parameter return instead an Either ErrorCode a. Modules are grouped roughly by the section in which they appear in the standard. I'm working on an OpenCL binding that is a little more cooked as well as a high-level OpenCL binding. OpenCL is a platform for single-host heterogenous, data-parallel computing that follows roughly the OpenGL and OpenAL conventions for how the library is architected. It will be available by default in the next version of Apple's OS-X, and there are drivers for AMD Opteron/Athlons and nVidia CUDA-based graphics cards. The basic procedure behind running an OpenCL program is: 1. get a list of platforms 2. choose a device on the platform that fits your needs 3. create a context for the platform and the device 4. compile a program and kernels written in OpenCL/C 5. create memory buffer objects. 6. execute kernels on the memory buffer objects. 7. rinse hands, repeat. Obviously this is not very functional, but we can't get there without a raw binding. Data Parallel computing is somewhere Haskell is excelling; hopefully this will generate some interest in creating a DPH binding to OpenCL's C99-based language, OpenCL/C. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Text.Html introduction
http://www.haskell.org/ghc/docs/latest/html/libraries/xhtml/Text-XHtml.html says: Based on the original Text.Html library by Andy Gill. See http://www.cse.ogi.edu/~andy/html/intro.htm for an introduction to that library. But that link gives a not-found page. Anyone know where it is know? -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Looking up functions inQ monad (Template Haskell).
Hello Zefirov, Tuesday, August 18, 2009, 5:55:19 PM, you wrote: Why isn't possible to lookup and call user-defined functions while performing Template Haskell actions? if i understood correctly what you mean - it's possible. the function just need to be defined in module imported by current one. defining and using function in the same module isn't supported since it may be tricky for language with global module analysis. Lisp just executes lists as it reads them, so it doesn't have such problem -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Planning for a website
I'm intending to replace my current website - which uses Drupal, with a hand-written-in-Haskell version this autumn, for a number of reasons (a principal one is the lack of an upgrade path in Drupal). So I'm currently looking into the libraries available to see how much I'll have to write myself. One problem will be to get GHC ported to DragonFly BSD, but that can wait until I have a test version of the site working on Linux. The next major challange is to implement something like Drupal's Image and Image Gallery modules. That doesn't seem to be a great problem, as the exif and GD libraries seem to cover everything I'll need. So my major decision is what framework and html-generating libraries to use. There is such a wide choice on the Haskell Wiki. But I guess some are more maintained than others. For instance, WASH attracts me, with it's guarantee of valid generated pages, but it isn't clear to me that it's actively maintained (last date I can see on the web pages is 2006). HappStack is obviously currently maintained, and since it seems to have a blogging module in development, that is attractive. HASP is maintained too, I think. Has anyone written a comparison of the various libraries, or gone through the same decision process recently? -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Text.Html introduction
On Tue, Aug 18, 2009 at 4:02 PM, Colin Paul Adamsco...@colina.demon.co.uk wrote: http://www.haskell.org/ghc/docs/latest/html/libraries/xhtml/Text-XHtml.html says: Based on the original Text.Html library by Andy Gill. See http://www.cse.ogi.edu/~andy/html/intro.htm for an introduction to that library. But that link gives a not-found page. Anyone know where it is know? I was looking for this page this morning and couldn't find it. Google does have it in its cache either. -- Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Planning for a website
Colin Paul Adams wrote: One problem will be to get GHC ported to DragonFly BSD, but that can wait until I have a test version of the site working on Linux. I would love to see this. It's the biggest thing blocking me from trying Dragonfly more seriously. WASH attracts me, with it's guarantee of valid generated pages, but it isn't clear to me that it's actively maintained (last date I can see on the web pages is 2006). You should look into HSP. It also provides those guarantees, is maintained, and provides a nice template-style syntax which you can use inline with your Haskell code. Also check out the Formlets library. HappStack is obviously currently maintained, and since it seems to have a blogging module in development, that is attractive. I recommend this. - Jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Planning for a website
I forgot to also mention this somewhat recent announcement for a pedantically type safe HTML library: http://www.haskell.org/pipermail/haskell-cafe/2009-August/064907.html - Jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Planning for a website
Jake == Jake McArthur jake.mcart...@gmail.com writes: Jake Colin Paul Adams wrote: One problem will be to get GHC ported to DragonFly BSD, but that can wait until I have a test version of the site working on Linux. Jake I would love to see this. It's the biggest thing blocking me Jake from trying Dragonfly more seriously. Well it will happen, as I have to use DragonFly, as my website is all about dragonflies :-) Someone has already got it working sufficiently to compile xmonad, so it should just be a matter of digging around the low-level issues. Jake You should look into HSP. It also provides those guarantees, Jake is maintained, and provides a nice template-style syntax Jake which you can use inline with your Haskell code. Jake Also check out the Formlets library. HappStack is obviously currently maintained, and since it seems to have a blogging module in development, that is attractive. Jake I recommend this. Thanks. -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
During a small project I'm trying to develop a small application. It becomes quite often that I need a function mapapp: mapapp _ [] ap = ap mapapp f (a:as) ap = f a : map f as ap Of course, (map f list) ++ append would do the same as mapapp f list append but with less efficiency. Or am I wrong? I timed each of the following five operations with ... ghc -O2 --make MapApp.hs time ./MapApp ... and they produced no statistically significant differences. Each ran for about 3.8 seconds. Perhaps you can try it to convince yourself? Sean -- module Main where mapapp0 :: (a - b) - [b] - [a] - [b] mapapp0 f tail xs = map f xs ++ tail mapapp1 :: (a - b) - [b] - [a] - [b] mapapp1 _ tail [] = tail mapapp1 f tail (a:as) = f a : mapapp1 f tail as mapapp2 :: (a - b) - [b] - [a] - [b] mapapp2 f tail = go where go [] = tail go (x:xs) = f x : go xs mapapp3 :: (a - b) - [b] - [a] - [b] mapapp3 f tail = foldr ((:) . f) tail main = do writeFile /dev/null $ show $ [1 .. 10001000] -- writeFile /dev/null $ show $ mapapp0 (+3) [1 .. 1000] [1 .. 1000] -- writeFile /dev/null $ show $ mapapp1 (+3) [1 .. 1000] [1 .. 1000] -- writeFile /dev/null $ show $ mapapp2 (+3) [1 .. 1000] [1 .. 1000] -- writeFile /dev/null $ show $ mapapp3 (+3) [1 .. 1000] [1 .. 1000] return () ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Library function for map+append
Hello Sean, Tuesday, August 18, 2009, 7:49:21 PM, you wrote: writeFile /dev/null $ show $ [1 .. 10001000] it may be dominated by show+writeFile. i suggest you to compute, say, sum of all elements instead -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Library function for map+append
2009/8/18 Dusan Kolar ko...@fit.vutbr.cz: Dlists maybe good it all the app is written using them. Probably not good idea to switch to them in the middle of project... I have a different criterion for DLists. I think they are best to use in small scopes (I think the same of monads), as opposed to interfacing between different parts of a project. A DList is well-suited when you are *outputting* a list using appends; i.e. just concatenating stuff together, but not looking at the heads or iterating over the lists. The DList Quicksort is a perfect example. It also makes a good monoid for Writer. toList it after you're done generating; this is an efficient operation. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Library function for map+append
On Tue, Aug 18, 2009 at 18:23, Bulat Ziganshin wrote: Hello Sean, Tuesday, August 18, 2009, 7:49:21 PM, you wrote: writeFile /dev/null $ show $ [1 .. 10001000] it may be dominated by show+writeFile. i suggest you to compute, say, sum of all elements instead Thank you, Bulat. The results now show some variation. Sean -- writeFile /dev/null $ show $ sum $ [1 .. 10001000] 0m1.652s 0m1.634s 0m1.658s writeFile /dev/null $ show $ sum $ mapapp0 (+3) [1 .. 1000] [1 .. 1000] 0m1.601s 0m1.613s 0m1.615s writeFile /dev/null $ show $ sum $ mapapp1 (+3) [1 .. 1000] [1 .. 1000] 0m1.647s 0m1.656s 0m1.654s writeFile /dev/null $ show $ sum $ mapapp2 (+3) [1 .. 1000] [1 .. 1000] 0m1.640s 0m1.645s 0m1.664s writeFile /dev/null $ show $ sum $ mapapp3 (+3) [1 .. 1000] [1 .. 1000] 0m1.541s 0m1.531s 0m1.561s ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: simulation in the haskell way
...) But for simulation kind-of problems, in which I think OO really fits the best, what's the haskell way to structure such problems? I once thought maybe I can use the State monad to simulate objects. But it's really hard for me to implement, because I think State monad is used to simulate a global shared state, is it right? Then what's the best way to simulate private states or just instead how to solve simulation problems such as a physical engine using the haskell way? A physical engine can be simulated using pure code, with a function from timestep to state. (Of course, that doesn't hold when you want to deal with user interaction.) I think there is no general answer to your question. My sugestion is to describe an example you would like to work with. Maurício ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Planning for a website
I can give a +1 vote for the Hack api and related libs. (Jinjing Wang is a one-man army.) Below hack you'll run happstack or another web-serving lib. Above hack you might run some combination of loli, maid, the hack middleware modules, hsp. The advantage is that changing the low-level server in future is a matter of changing one or two lines; and the upper-level utilities seem more usable to me than current happstack's. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Planning for a website
I'd also give a read to this website: http://jekor.com/article/is-haskell-a-good-choice-for-web-applications Interesting read about a guy who actually used Haskell to create his website from the ground up. On Tue, Aug 18, 2009 at 9:56 AM, Colin Paul Adams co...@colina.demon.co.ukwrote: Jake == Jake McArthur jake.mcart...@gmail.com writes: Jake Colin Paul Adams wrote: One problem will be to get GHC ported to DragonFly BSD, but that can wait until I have a test version of the site working on Linux. Jake I would love to see this. It's the biggest thing blocking me Jake from trying Dragonfly more seriously. Well it will happen, as I have to use DragonFly, as my website is all about dragonflies :-) Someone has already got it working sufficiently to compile xmonad, so it should just be a matter of digging around the low-level issues. Jake You should look into HSP. It also provides those guarantees, Jake is maintained, and provides a nice template-style syntax Jake which you can use inline with your Haskell code. Jake Also check out the Formlets library. HappStack is obviously currently maintained, and since it seems to have a blogging module in development, that is attractive. Jake I recommend this. Thanks. -- Colin Adams Preston Lancashire ___ 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
[Haskell-cafe] Keeping an indexed collection of values?
I've been in a situation a lot lately where I need to keep a collection of
values, and keep track of them by a persistent index.
IO and ST refs can do this, but for various reasons I can't/don't want to
use them.
My first hacked up attempt is as follows:
data IndexedCollection a = IndexedCollection {
nextKey:: Int,
availableKeys :: [Int],
items:: (IntMap Int a)
} deriving (Show)
emptyIndexedCollection :: IndexedCollection a
emptyIndexedCollection = IndexedCollection 0 [] empty
addItem :: a - IndexedCollection a - (Int, IndexedCollection a)
addItem a (IndexedCollection nextKey' [] t) = (nextKey',
IndexedCollection (nextKey' + 1) [] (insert nextKey' a t))
addItem a (IndexedCollection nextKey' (k:ks) t) = (k, IndexedCollection
nextKey' ks (insert k a t))
removeItem :: Int - IndexedCollection a - IndexedCollection a
removeItem k (IndexedCollection nextKey' ks t) = IndexedCollection nextKey'
(k:ks) (delete k t)
lookupItem :: Int - IndexedCollection a - Maybe a
lookupItem k (IndexedCollection _ _ t) = lookup k t
Basically: when you add an item, use the first index in availableKeys (if
there is one), otherwise use nextKey for the index, and then increment it
for the next item.
When and Item is removed, add it's index to availableKeys
This keeps the code for keeping track of/generating indexes hidden away from
the rest of the program which is nice, and it remains fairly efficient.
Items will be added and removed on very regular basis. Often enough that I'm
slightly concerned about overflow of nextKey for very long run times, and
hence the availableKeys list.
Does anyone know of a better/already existent data structure for handling
this problem?
Or perhaps a better way of keeping a key pool than my availableKeys
solution?
- Job
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Planning for a website
Simon Michael si...@joyful.com writes: I can give a +1 vote for the Hack api and related libs. (Jinjing Wang is a one-man army.) Below hack you'll run happstack or another web-serving lib. Above hack you might run some combination of loli, maid, the hack middleware modules, hsp. The advantage is that changing the low-level server in future is a matter of changing one or two lines; and the upper-level utilities seem more usable to me than current happstack's. The problem is that `hack` isn't documented at all and that prevents it from being in wide use. At least, when I started my web app, I preferred happstack, as low-level and documented API is better than high-level API without a little bit of documentation, examples and tutorials. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: simulation in the haskell way
On Tuesday 18 August 2009, Maurício CA wrote: ...) But for simulation kind-of problems, in which I think OO really fits the best, what's the haskell way to structure such problems? I once thought maybe I can use the State monad to simulate objects. But it's really hard for me to implement, because I think State monad is used to simulate a global shared state, is it right? Then what's the best way to simulate private states or just instead how to solve simulation problems such as a physical engine using the haskell way? A physical engine can be simulated using pure code, with a function from timestep to state. (Of course, that doesn't hold when you want to deal with user interaction.) I think there is no general answer to your question. My sugestion is to describe an example you would like to work with. Hi, I did a medium sized mobility models simulator this way. The simulation is represented as an infinite list of states, where the next state is created by applying a state transformation (next) function to the previous state. This has the advantage that you can calculate values based on more than one state. The downside is that if you need to look back 100 stesp, you need to remember 100 states (though if enough of it is unchanged and shared then it's not really that much of a problem). As far as the details go -- different parts of the simulator are executed in different monads. god-mode code, like the next function has the type nextStep :: World - World but the mobility model implementation (which tells a node how to move) is a stateful computation run by nextStep: mobilityModel :: StateT NodeState (Reader World) () But as Maurício said -- please describe what you want to achieve. At least what kind of simulation you'd like to write. -- Thanks! Marcin Kosiba signature.asc Description: This is a digitally signed message part. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Installing documentation with cabal
Is it possible to automatically (or non-automatically) install documentation when installing package with cabal-install? Regards signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Installing documentation with cabal
It is. From command line: cabal install package --enable-documentation or add line documentation: True to .cabal/config or equivalent. Best regards Krzysztof Skrzętnicki On Tue, Aug 18, 2009 at 22:29, Maciej Piechotka uzytkown...@gmail.comwrote: Is it possible to automatically (or non-automatically) install documentation when installing package with cabal-install? Regards ___ 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] Installing documentation with cabal
On Tue, 2009-08-18 at 22:37 +0200, Krzysztof Skrzętnicki wrote: It is. From command line: cabal install package --enable-documentation or add line documentation: True to .cabal/config or equivalent. Best regards Krzysztof Skrzętnicki Thanks a lot. Regards signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type family signatures
On Mon, Aug 17, 2009 at 12:12 AM, Thomas van Noorttho...@cs.ru.nl wrote: Somehow I didn't receive David's mail, but his explanation makes a lot of sense. I'm still wondering how this results in a type error involving rigid type variables. rigid type means the type has been specified by the programmer somehow. Desugaring your code a bit, we get: GADT :: forall a b. (b ~ Fam a) = a - b - GADT b Notice that this is an existential type that partially hides a; all we know about a after unwrapping this type is that (Fam a ~ b). unwrap :: forall a b. (b ~ Fam a) = GADT b - (a,b) unwrap (GADT x y) = (x,y) So, the type signature of unwrap fixes a and b to be supplied by the caller. Then the pattern match on GADT needs a type variable for the existential, so a new a1 is invented. These are rigid because they cannot be further refined by the typechecker; the typechecker cannot unify them with other types, like a1 ~ Int, or a1 ~ a. An example of a non-rigid variable occurs type-checking this expression: foo x = x + (1 :: Int) During type-checking/inference, there is a point where the type environment is: (+) :: forall a. Num a = a - a - a b :: *, non-rigid x :: b c :: *, non-rigid foo :: b - c Then (+) gets instantiated at Int and forces b and c to be Int. In your case, during the typechecking of unwrap, we have: unwrap :: forall a b. (b ~ Fam a) = GADT b - (a,b) a :: *, rigid b :: *, rigid (b ~ Fam a) -- From the pattern match on GADT: a1 :: *, rigid x :: a1 y :: b (b ~ Fam a1) Now the typechecker wants to unify a and a1, and it cannot, because they are rigid. If one of them was still open, we could unify it with the other. The type equalities give us (Fam a ~ Fam a1), but that does not give us (a ~ a1). If Fam was a data type or data family, we would know it is injective and be able to derive (a ~ a1), but it is a type family, so we are stuck. -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell-beginners] Start file with associated prog (windows only?)
Max Desyatov wrote: Bernhard Lehnert b.lehn...@gmx.de writes: Windows has a command start which you can use e.g. via System.Process.proc. Thank you, Magnus - this is exactly what I was looking for. (By the way, someone should implement something like this for GNOME and KDE, too ;-) ) You can do that using MIME, look at /etc/mailcap, it already contains all what you need to run appropriate process for exact MIME-type. As long as it's supported in your distribution. Is there a command line interface for that? Or maybe a lib that's easy to wrap? If you want to query the Gnome MIME database (which is separate from /etc/mailcap) you can use 'xdg-mime'. /M -- Magnus Therning(OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe signature.asc Description: OpenPGP digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re : [Haskell-cafe] simulation in the haskell way
Then what's the best way to simulate private states or just instead how to solve simulation problems such as a physical engine using the haskell way? perhaps Hipmunk ? http://hackage.haskell.org/package/Hipmunk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: simulation in the haskell way
I used to think about a physical engine in a similar way, and I think it can work. But in some simulations that objects have lots of dependencies on others can be tricky. For instance, object o1 depends on o2, if we represent them in pure values, when we update o2, then o1 must be updated with a new o2 value, isn't it? Recently I want to implement the digital circuit simulation in SICP using Haskell as an exercise. In the Scheme version, each Wire is represented as a function with local states. It records the signal on the wire and actions it will take when the signal changes to activate other wires. How to represent the Wire in haskell purely? If I use State Monad (yes, it's pure :) to repsent a wire with local state, the interaction between connected wires is really tricky to implement. any ideas? thanks. Eric ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Text.Html introduction
Here is something: http://cpansearch.perl.org/src/AUTRIJUS/Language-Haskell-0.01/hugs98-Nov2003/fptools/hslibs/text/html/doc/doc.htm (Link found in an old haskell-cafe message) Sjoerd On Aug 18, 2009, at 4:18 PM, Johan Tibell wrote: On Tue, Aug 18, 2009 at 4:02 PM, Colin Paul Adamsco...@colina.demon.co.uk wrote: http://www.haskell.org/ghc/docs/latest/html/libraries/xhtml/Text-XHtml.html says: Based on the original Text.Html library by Andy Gill. See http://www.cse.ogi.edu/~andy/html/intro.htm for an introduction to that library. But that link gives a not-found page. Anyone know where it is know? I was looking for this page this morning and couldn't find it. Google does have it in its cache either. -- Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Sjoerd Visscher sjo...@w3future.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: simulation in the haskell way
You could read: http://www.cs.nott.ac.uk/~nhn/FoPAD2007/Talks/nhn-FoPAD2007.pdf http://haskell.cs.yale.edu/yale/papers/haskell-workshop03/yampa-arcade.pdf http://www.cs.nott.ac.uk/~nhn/Talks/HW2002-FRPContinued.pdf http://www.haskell.org/yale/papers/haskellworkshop02/index.html http://www.haskell.org/haskellwiki/Frag Basically, even in an imperative solution, if you have complex dependencies between objects at the same time T, then my experience tells me your into trouble, it's better to make all objects at time T depend on the state of other objects at time T-dT. If you absolutely need to know at time T what the state of another object is at time T, the network of dependencies needs to be rearranged dynamically, and you might get different results (or endless loops if you do it badly) in the case of mutual dependencies. This is what Elerea does. On Wed, Aug 19, 2009 at 12:40 AM, Eric Wong wsy...@gmail.com wrote: I used to think about a physical engine in a similar way, and I think it can work. But in some simulations that objects have lots of dependencies on others can be tricky. For instance, object o1 depends on o2, if we represent them in pure values, when we update o2, then o1 must be updated with a new o2 value, isn't it? Recently I want to implement the digital circuit simulation in SICP using Haskell as an exercise. In the Scheme version, each Wire is represented as a function with local states. It records the signal on the wire and actions it will take when the signal changes to activate other wires. How to represent the Wire in haskell purely? If I use State Monad (yes, it's pure :) to repsent a wire with local state, the interaction between connected wires is really tricky to implement. any ideas? thanks. Eric ___ 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
[Haskell-cafe] Re: simulation in the haskell way
Eric Wong wsy...@gmail.com wrote: I used to think about a physical engine in a similar way, and I think it can work. But in some simulations that objects have lots of dependencies on others can be tricky. For instance, object o1 depends on o2, if we represent them in pure values, when we update o2, then o1 must be updated with a new o2 value, isn't it? This is something handled best by functional reactive programming. See Peter Verswyvelen's post. It allows you to encode this purely in an excitingly elegant way. Recently I want to implement the digital circuit simulation in SICP using Haskell as an exercise. In the Scheme version, each Wire is represented as a function with local states. It records the signal on the wire and actions it will take when the signal changes to activate other wires. How to represent the Wire in haskell purely? If I use State Monad (yes, it's pure :) to repsent a wire with local state, the interaction between connected wires is really tricky to implement. any ideas? You don't. Either you use a state monad to hold _all_ wires (objects) in, say, a Map, a Set or an Array, or you use a completely different approach (like FRP). In other words, your state monad should represent all wires, not just one, because all wires together make up the state you want to work with. Greets, Ertugrul. -- nightmare = unsafePerformIO (getWrongWife = sex) http://blog.ertes.de/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: simulation in the haskell way
It is interesting to note that recent work on AFRP (arrow-based FRP) - namely Causal Commutative Arrows - optimizes a complete circuit of arrows (interconnected objects if you prefer to think that way) that all have local state and local feedback loops into one large state and feedback loop, essentially what optimized imperative simulations also do (e.g. thousands of moving particles that are treated as a single state block of position/velocity pairs). Together with stream fusion the researchers working on this were able to generate optimized code that runs hundreds (!!!) times faster than the best GHC could do. Impressive isn't it. Unfortunately it will only work on static networks, not those with dynamic switches in it, but I'm pretty sure that within say 5 years, this will all be settled and it will become exiting times for simulation developers, we will finally be pure, lazy *and* fast; it just needs a little push (since it's now mostly pulling, okay I'll stop the nonsense, couldn't resist the nerd talk ;-) On Wed, Aug 19, 2009 at 1:29 AM, Ertugrul Soeylemez e...@ertes.de wrote: Eric Wong wsy...@gmail.com wrote: I used to think about a physical engine in a similar way, and I think it can work. But in some simulations that objects have lots of dependencies on others can be tricky. For instance, object o1 depends on o2, if we represent them in pure values, when we update o2, then o1 must be updated with a new o2 value, isn't it? This is something handled best by functional reactive programming. See Peter Verswyvelen's post. It allows you to encode this purely in an excitingly elegant way. Recently I want to implement the digital circuit simulation in SICP using Haskell as an exercise. In the Scheme version, each Wire is represented as a function with local states. It records the signal on the wire and actions it will take when the signal changes to activate other wires. How to represent the Wire in haskell purely? If I use State Monad (yes, it's pure :) to repsent a wire with local state, the interaction between connected wires is really tricky to implement. any ideas? You don't. Either you use a state monad to hold _all_ wires (objects) in, say, a Map, a Set or an Array, or you use a completely different approach (like FRP). In other words, your state monad should represent all wires, not just one, because all wires together make up the state you want to work with. Greets, Ertugrul. -- nightmare = unsafePerformIO (getWrongWife = sex) http://blog.ertes.de/ ___ 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: simulation in the haskell way
Thanks for all your post. When I was using C and Python, I used to think of most applications in an simulation way. I think it's right to say that programs are simulations. But now I have to change my mind in Haskell, I have to think in a data-flow way, that is: data in, processing using function composition, data out. Even true simulation should be seen in such a perspective, right? And of course, I have to learn about FRP. Thanks, Eric ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: simulation in the haskell way
2009/08/18 Eric Wong wsy...@gmail.com: When I was using C and Python, I used to think of most applications in an simulation way. By simulation way, do you mean object-oriented way? -- Jason Dusek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: simulation in the haskell way
On Tue, Aug 18, 2009 at 5:19 PM, Eric Wongwsy...@gmail.com wrote: Thanks for all your post. When I was using C and Python, I used to think of most applications in an simulation way. I think it's right to say that programs are simulations. On a philosophical note, this is a sign of expertise. Humans tend to think of the world, and things in, in the way that they understand things in their area of expertise. If you develop expertise in Haskell (or FP in general) you will like begin to see things in functional ways. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: simulation in the haskell way
When I was using C and Python, I used to think of most applications in an simulation way. I think it's right to say that programs are simulations. But now I have to change my mind in Haskell, I have to think in a data-flow way, that is: data in, processing using function composition, data out. You have to think there's no in and out, since there's no state and so no before and after. And no flow, since time is just an ilusion of users. In Haskell, a program just is. Sorry, could not resist the Jedi talk... Hope you like the language. Best, Maurício ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: simulation in the haskell way
By simulation way, do you mean object-oriented way? they are similar, but not equal, I think. OO is great for simulation, but simulation does not necessarily use OO. Virtual machine simulates real machines, you can use OO language to do it, but most use C in the real world I think. So, simulation way is more like an imperative way. But it also relates to what do you mean by simulation. If we are simulating things in the physics world, then it's most likely imperative, and most of the time an OO way. Because the physics world are more natrual in such a perspective. But if we are simulating the way people doing things, it may not necessarily be imperative. For instance Mathematics, It's more natural to simulate in a functional way. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: simulation in the haskell way
Sorry for a mistake. Shiyou Wang is my identity in a private chinese group. Sorry for the confusing. :-( Eric ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Control.Parallel on 6.10.4 - Mac OS X version
I'm using the Control.Parallel package on ghc version 6.10.4 and I don't seem to be getting any parallel threads or sparks created at all with the -threaded compilation option using runtime flags +RTS -N2. I'm using simple examples from the paper A Tutorial on Parallel and Concurrent Programming in Haskell by Jones and Singh. I'm running on an Intel Mac core 2 duo. Does anyone know how I can check if the parallel functionality in ghc is working on my 6.10.4 ghc package installed on this platform ? I installed it from the supported runtime pkg for OS X from the ghc website. thanks ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Control.Parallel on 6.10.4 - Mac OS X version
k2msmith: I'm using the Control.Parallel package on ghc version 6.10.4 and I don't seem to be getting any parallel threads or sparks created at all with the -threaded compilation option using runtime flags +RTS -N2. I'm using simple examples from the paper A Tutorial on Parallel and Concurrent Programming in Haskell by Jones and Singh. I'm running on an Intel Mac core 2 duo. Does anyone know how I can check if the parallel functionality in ghc is working on my 6.10.4 ghc package installed on this platform ? I installed it from the supported runtime pkg for OS X from the ghc website. A simple parallel 'hello world' http://haskell.org/haskellwiki/Haskell_in_5_steps#Write_your_first_parallel_Haskell_program ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Observations about foldM
[This message is literate Haskell] Hi -cafe, I was trying to use Monad.foldM in the State monad recently and ran into some performance issues. They were eventually fixed with seq, but along the way I made some discoveries, which I thought I would share. The Report defines foldM as foldM :: (Monad m) = (a - b - m a) - a - [b] - m a foldM f z [] = return z foldM f z (x:xs) = f z x = \z' - foldM f z' xs It turns out that foldM is essentially a right fold. Define f' = \h t - flip f h = t. The operator (=) is (reverse) Kleisli composition, defined in Control.Monad as f = g = \x - f x = g. Now foldM f z xs = foldr f' return xs z. Proof. On the empty list, foldM f z [] = return z [definition of foldM] = foldr f' return [] z [definition of foldr] Now fix a list xs and inductively assume that foldM f z xs = foldr f' return xs z for all z. Then for any z and x, foldM f z (x:xs) = f z x = \z' - foldM f z' xs [definition of foldM] = f z x = \z' - foldr f' return xs z' [inductive hypothesis] = f z x = foldr f' return xs [eta-conversion(*)] = flip f x z = foldr f' return xs [definition of flip] = (\z' - flip f x z' = foldr f' return xs) z [beta-reduction] = (flip f x = foldr f' return xs) z [definition of =] = (f' x (foldr f' return xs)) z [definition of f'] = foldr f' return (x:xs) z [definition of foldr] (*) The eta-conversion preserves strictness as long as return /= _|_, since f = g is in WHNF. Interestingly, foldM can also be written as a left fold. To see this, note that it is a theorem that foldr f z xs = foldl f z xs as long as f is associative and z is a unit for f. Since (=) is associative with unit return, we have foldr (\h t - flip f h = t) return = foldr (=) return . map (flip f) [foldr/map fusion] = foldl (=) return . map (flip f) [by the theorem] = foldl (\t h - t = flip f h) return [foldl/map fusion] Therefore foldM f z xs = foldr f' return xs z = foldl f'' return xs z, where f'' = \t h - t = flip f h. But this doesn't mean these all have the same performance characteristics. Exercise for the reader: find examples where the foldr version performs better than the foldl version and vice-versa. I've noticed this distinction between State and [] in particular. They both may require use of seq in the function f to prevent stack overflow. Here is a module implementing these versions of foldM. It seems reasonable to have versions with = and with f unflipped as well, but those could be derived from the functions below. module FoldM (foldrM, foldr1M, foldlM, foldl1M) where import Control.Monad((=)) -- foldrM nests to the right: -- foldrM f z [x1, ..., xn] = (flip f x1 = (... = (flip f xn)...)) $ z foldrM :: Monad m = (a - b - m a) - a - [b] - m a foldrM f z xs = foldr (\h t - flip f h = t) return xs z Surprisingly, this may or may not be faster than the equivalent foldrM f z = return z = foldr (\h t - flip f h = t) return xs depending on the monad. But they're both slower than foldM. foldr1M f (x:xs) = foldrM f x xs -- foldlM nests to the left: -- foldlM f z [x1, ..., xn] = (...(flip f x1) = ...) = flip f xn) $ z foldlM :: Monad m = (a - b - m a) - a - [b] - m a foldlM f z xs = foldl (\t h - t = flip f h) return xs z Again, this is apparently faster or slower than either of foldlM f z xs = return z = foldl (\t h - t = flip f h) return xs foldlM f = foldl (\t h - t = flip f h) . return depending on the monad. foldl1M f (x:xs) = foldlM f x xs -- Jason McCarty jmcca...@sent.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
