[Haskell-cafe] Re: Help with IO and randomR
Bryan Burgers wrote: I did not look at it long enough to tell you why there is an infinite loop. However, think about it on a high level with me. You want a stream of these random numbers (I'm not sure what a triangular distribution is, but that's okay). To get one of these, you take two random numbers and perform a combination function (\x y - (x + y) `div` 2 ) on them. Yes, precisely. Triangular distribution is a probability distribution that is equivalent to two rolls of dice. This means that the numbers at the middle of the range are much more likely to pop up than numbers at the edge of the range. It is quite close to gaussian distribution. I'm toying around with a signal processing toolkit in Haskell. The noise I'm trying to generate here is needed for a process called dithering, in which some noise is added to a quantized signal in order to improve it's accuracy. But not just any kind of noise will do for this purpose. The best noise for dithering is noise with triangular or gaussian probability distribution, instead of white noise which has equal probability distribution. But, like you said, that's not really important for the purposes of this discussion. What is is that we take a bunch of random numbers, perform some mathematical operation on them in order to introduce some statistical properties to the series and return the processed series. There are several different probability distribution functions, triangular being one of them. Triangular distribution requires two random numbers to generate one, and some functions require more than that. So you can lift this from one random numbers to a stream of random numbers if you have have two streams of random numbers instead of just two random numbers. zipWith is the function that brings us from one number to a stream of numbers. tpdfs range = do g - newStdGen -- get a random generator (g1, g2) - return $ split g -- make two random generators out of it return $ zipWith combine (randomRs range g1) (randomRs range g2) -- get two streams of random numbers, and combine them elementwise. combine x y = (x + y) `div` 2 So, moving on to the next question, how well do you think this solution would scale if we would need n random numbers to generate one? Niko ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Help with IO and randomR
Tillmann Rendel wrote: (A) will be executed before (B) because of the IO monad. But you want r to be returned before rest is computed. I would split tpdfs in two functions: a pure function converting a infinite list of random numbers to another infinite list of random numbers, and an IO-function creating the original infinite list of random numbers: tpdfs' :: [Int] - [Int] tpdfs' (x:y:rest) = (x + y) `div` 2 : tpdfs' rest tpdfs :: (Int, Int) - IO [Int] tpdfs range = do gen - newStdGen return (tpdfs' (randomRs range gen)) This seems like a good solution since it scales well with probability functions that require more than two random numbers in order to produce one. I could just write different versions of tpdfs' to process the stream and feed the functions to tpdfs. Nice. I'm not sure your aproach is numerically correct. Let's assume range = (0, 1). The resulting number could be (0 + 0) `div` 2 = 0 (0 + 1) `div` 2 = 0 (1 + 0) `div` 2 = 0 (1 + 1) `div` 2 = 1 with equal probability. Is this what you want? Come to think of it, a better formula would be something like: round(x/2 + y/2) round(0/2 + 0/2) = 0 round(0/2 + 1/2) = round(0.5) = 1 round(1/2 + 0/2) = round(0.5) = 1 round(1/2 + 1/2) = = 1 But that's only because of rounding issues. Otherwise this is exactly what I want. Triangular distribution is equivalent to two rolls of dice, meaning that numbers at the middle of the range are much more likely to pop up than numbers at the edge of the range. Quite like in gaussian probability distribution. It's just that the range (0, 1) is too short for the function to work properly with integer arithmetics. It's difficult to say what the middle of the range (0, 1) should be. If we always round the result to the nearest integer, the middle of the range is 1. The fixed formula demostrates that the numbers at the middle of the range (round(0.5)) are most likely to appear. Niko ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] More on improving the mailing list
An interesting study on problem resolution and feedback on some technical mailing lists, How to Help Mailing Lists Help Readers (Results of Recent Data Analysis) http://praxagora.com/andyo/professional/mailing_list_follow_up/ including graphs! :) With conclusions at the end on how to improve mailing lists by /integrating material into wikis/, and providing both theoretical and practical advice for a given problem. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell for categorists
Miguel Mitrofanov miguelimo38 at yandex.ru writes: Just being curious. There are a lot of tutorials ensuring the reader that, although Haskell is based on category theory, you don't have to know CT to use Haskell. So, is there ANY Haskell tutorial for those who do know CT? I don't need it, personally, but still... There's the papers by Meijer, Paterson, Fokkinga etc. E.g. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Perhaps topical given the recent discussions on co-recursion. Dominic. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] RE: haskell for web
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of ??? help haskell for web code http://www.haskell.org/haskellwiki/Applications_and_libraries/Web_programming Try a few of these out (whatever meets your needs). For web apps WASH and HAppS seem popular. Feel free to ask the haskell-café list for further help. 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] A really bad way to say all isSpace
Hi Reading through the code to lex, it appear that it will return [(,)] if and only if all isSpace t. If this is really the case, does it make sense to state all isSpace t? It has a much clearer meaning to me. I think 'lex' is supposed to not understand (haskell-style) comments - which I agree with - so I agree that it would be better to say (all isSpace t). I might even have thought that in passing when reading that code, I don't remember My particular reason for wanting this is that read :: Int - String depends on lex, when logically reading an Int doesn't appear to warrant lexing Haskell! Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: hMapping polymorphic functions
hMapping polymorphic functions is indeed quite challenging, but can be done. That was the topic of the message Type-class overloaded functions: second-order typeclass programming with backtracking http://okmij.org/ftp/Haskell/poly2.txt The challenge is how to avoid specifying the context too early or at all and keep the context to the bare minimum. Your particular case is simple however: applying the function (\x-[x]) that applies literally to any argument type and is defined only by one case: data FnListify = FnListify instance TypeCast [a] r = Apply FnListify a r where apply _ x = typeCast [x] list1 = 'a' :*: a :*: True :*: HNil test1 = hMap FnListify list1 *Poly2 test1 a :*: ([a] :*: ([True] :*: HNil)) Within the Poly2 framework, the example becomes data FnListify = FnListify instance TypeCast Otherwise r = GFN n FnListify a r instance TypeCast [a] r = Apply (GFnA n FnListify) a r where apply _ x = typeCast [x] instance TypeCast [a] r = Apply FnListify a r where apply _ x = typeCast [x] test2 = hMap (GFn FnListify) list1 *Poly2 test2 a :*: ([a] :*: ([True] :*: HNil)) The advantage of making things more complicated than they are is that we can add more clauses to our generic function. For example, we may choose to handle Booleans in a different way, by negating them. We add (perhaps in a different module, so the original code remains as it was) data OnlyBool instance TypeCast OnlyBool r = GFN Z FnListify a r instance Apply OnlyBool Bool HTrue instance TypeCast HFalse r = Apply OnlyBool a r instance Apply (GFnA Z FnListify) Bool Bool where apply _ x = not x and now, *Poly2 test2 a :*: ([a] :*: (False :*: HNil)) P.S. It may be worth sending me a carbon copy (CC) of any question relating to HList, OOHaskell, continuations, etc. I can no longer afford reading every message on Haskell-Cafe (or even every tenth message). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
And this is where I think Haskell has it all over C++, Java, and the rest. Haskell is easy to learn at a simple level, and hard to learn at the expert level, but once learned is very powerful and has excellent payoffs in terms of productivity. With C++ or Java, the expertise is somewhat easier to acquire, but you never get the payoff. That may be true of Java, but it's not of C++. C++'s language specification is so big, it's almost too big to fit in one person's brain. It takes many years of studied confusion and a particularly anal frame of mind to work out what it, and what isn't, legal. And to top it off, it has a small pattern-matching pure-functional language with type classes built in that only runs at compile time. And that's before you get started on learning the various modern idioms you need to learn to stop C++ from burning you on the arse. And before you all flame, yes, I do know C++ at an expert level, and that is exactly why, after 7 years of writing server software in C++, I now want to do it in Haskell. Me too, which is why I find your statement that expertise in C++ is easy to acquire. Seeing some of my colleagues' code is enough to tell me that this is most definitely not the case. Martin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: haskell for web
On 7/17/07, Bayley, Alistair [EMAIL PROTECTED] wrote: From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of ??? help haskell for web code http://www.haskell.org/haskellwiki/Applications_and_libraries/Web_programming Try a few of these out (whatever meets your needs). For web apps WASH and HAppS seem popular. Feel free to ask the haskell-café list for further help. I wonder why 'we' aren't pushing things like this big time. When Ruby took off, more than anything else it was because of Rails. Web programming is something 'the kids' can really get into, and it caused Ruby to explode into the mainstream geek consciousness. Maybe the Haskell community should push something like Happs or Wash in the same way. Martin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
答复: [Haskell-cafe] RE: haskell for web
Haskell On Rails -邮件原件- 发件人: Martin Coxall [mailto:[EMAIL PROTECTED] 发送时间: 2007年7月17日 16:44 收件人: Bayley, Alistair 抄送: 王清军; [EMAIL PROTECTED]; haskell Café 主题: Re: [Haskell-cafe] RE: haskell for web On 7/17/07, Bayley, Alistair [EMAIL PROTECTED] wrote: From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of ??? help haskell for web code http://www.haskell.org/haskellwiki/Applications_and_libraries/Web_prog ramming Try a few of these out (whatever meets your needs). For web apps WASH and HAppS seem popular. Feel free to ask the haskell-café list for further help. I wonder why 'we' aren't pushing things like this big time. When Ruby took off, more than anything else it was because of Rails. Web programming is something 'the kids' can really get into, and it caused Ruby to explode into the mainstream geek consciousness. Maybe the Haskell community should push something like Happs or Wash in the same way. Martin Powered by MessageSoft SMG SPAM, virus-free and secure email Powered by MessageSoft SMG SPAM, virus-free and secure email ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
答复: [Haskell-cafe] RE: haskell for web
why 'Haskell On Rails' ? -邮件原件- 发件人: Martin Coxall [mailto:[EMAIL PROTECTED] 发送时间: 2007年7月17日 16:44 收件人: Bayley, Alistair 抄送: 王清军; [EMAIL PROTECTED]; haskell Café 主题: Re: [Haskell-cafe] RE: haskell for web On 7/17/07, Bayley, Alistair [EMAIL PROTECTED] wrote: From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of ??? help haskell for web code http://www.haskell.org/haskellwiki/Applications_and_libraries/Web_prog ramming Try a few of these out (whatever meets your needs). For web apps WASH and HAppS seem popular. Feel free to ask the haskell-café list for further help. I wonder why 'we' aren't pushing things like this big time. When Ruby took off, more than anything else it was because of Rails. Web programming is something 'the kids' can really get into, and it caused Ruby to explode into the mainstream geek consciousness. Maybe the Haskell community should push something like Happs or Wash in the same way. Martin Powered by MessageSoft SMG SPAM, virus-free and secure email Powered by MessageSoft SMG SPAM, virus-free and secure email ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Powered by MessageSoft SMG SPAM, virus-free and secure email Powered by MessageSoft SMG SPAM, virus-free and secure email ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] External Sort and unsafeInterleaveIO
hi folks --
a haskell newbie here, searching for comments and wisdom on my code.
i had a project to try to implement external sort in haskell as a
learning exercise. (external sort is sorting a list that is too large
to fit in main memory, by sorting in chunks, spooling to disk, and
then merging. more properly there probably should be multiple stages,
but for simplicity i'm doing a one-stage external sort.)
the trick is the number of files can quickly grow very large, so it is
best to use one large file and seek inside it around. however as one
can imagine the order-of-IO-operations becomes a bit tricky, if you're
seeking file handles around underneath Data.ByteString.Lazy's nose.
but late this night after not thinking about it for a while i had a
brainstorm: rewrite hGetContents to keep the handle position in the
right place! it's all about judicious use of unsafeInterleaveIO.
it seems to be rather fast, strangely faster than the usual sort at
times. it also seems to have nice memory characteristics, though not
perfect. it's hard to test because the normal sort function takes
too much RAM on large lists, making my computer swap like mad.
i'd appreciate any testing, comments and suggestions from the haskell
gods out there. my thanks to the Data.ByteString.Lazy, Data.Binary,
and Data.Edison people, who made this rather easy, once I grokked
unsafeInterleaveIO.
thanks and take care, B
module ExternalSort where
Sort a list of Ords offline. We're doing this to be able to sort
things without taking up too much memory (for example sorting lists
too large to fit in RAM.) Laziness is imperative, as is the
order-of-operations.
import Control.Monad
import Data.List
import qualified Data.Binary as Bin
import qualified Data.ByteString.Lazy as B
import qualified Data.ByteString as P (hGetNonBlocking, null)
import Data.ByteString.Base (LazyByteString(LPS))
import Foreign.Storable (sizeOf)
import System.IO (openFile, hClose, hSeek, hTell, hIsEOF, hWaitForInput,
Handle, IOMode(ReadMode, WriteMode),
SeekMode(AbsoluteSeek))
import System.IO.Unsafe (unsafeInterleaveIO)
import qualified Data.Edison.Seq.ListSeq as LS
import qualified Data.Edison.Coll.SplayHeap as Splay
Conceptually, we sort a list in blocks, spool blocks to disk, then
merge back. However for IO performance it is better to read off
chunks of elements off the sorted blocks from disk instead of
elements-at-a-time.
It would be better if these were in KBytes instead of # of elements.
blocksize :: Int
blocksize = 1
Turn a list into a list of chunks.
slice :: Int - [a] - [[a]]
slice _ [] = []
slice size l = (take size l) : (slice size $ drop size l)
Turn a list into a list of blocks, each of which is sorted.
blockify :: (Ord a) = Int - [a] - [[a]]
blockify bsize l = map sort $ slice bsize l
Serialize a block, returning the (absolute) position of the start.
dumpBlock :: (Ord a, Bin.Binary a) = Handle - [a] - IO Integer
dumpBlock h b = do
start - hTell h
B.hPut h $ Bin.encode b
return start
The actual sorting function. We blockify the list, turning it into a
list of sorted blocks, and spool to disk, keeping track of offsets.
We then read back the blocks (lazily!), and merge them.
externalSort [] = do return []
externalSort l = do
h - openFile ExternalSort.bin WriteMode
idx - mapM (\x - dumpBlock h x) (blockify blocksize l)
hClose h
h - openFile ExternalSort.bin ReadMode
blocks - mapM (\x - do {bs - hGetContentsWithCursor h x;
return $ Bin.decode bs}) idx
return (kMerge $ blocks)
Merging chunks. K-way merge (and in fact external sort in general) is
detailed in Knuth, where he recommends tournament trees. The easiest
thing is to probably use one of Okasaki's heaps. I'll use splay
heaps, because I don't know any better.
It would be better if I changed Ord for blocks to only check the first
element.
kMerge :: (Ord a) = [[a]] - [a]
kMerge [] = []
kMerge l =
let h = Splay.fromSeq l in
kM (Splay.minElem h) (Splay.deleteMin h)
where
kM :: (Ord a) = [a] - Splay.Heap [a] - [a]
kM l h
| h == Splay.empty = l
| otherwise =
let next = Splay.minElem h
(f, b) = span (\x - x = head next) l
in
f ++ (kM next (if null b then Splay.deleteMin h
else (Splay.insert b $ Splay.deleteMin h)))
kMergeSort :: (Ord a) = [a] - [a]
kMergeSort l = kMerge $ blockify blocksize l
This is a version of hGetContents which resets its handle position
between reads, so is safe to use with interleaved handle seeking.
hGetContentsWithCursor :: Handle - Integer - IO B.ByteString
hGetContentsWithCursor = hGetContentsWithCursorN defaultChunkSize
hGetContentsWithCursorN :: Int - Handle - Integer - IO B.ByteString
hGetContentsWithCursorN k h start = (lazyRead start) = return . LPS
where
lazyRead start = unsafeInterleaveIO $ loop start
loop start =
RE: [Haskell-cafe] -O2 compile option can give speed increase over -O. Fasta shootout program test runs.
| It seems the -O2 option can give a significant speed increase relative | to just the -O option. This is contrary to the documentation which says -O2 switches on SpecConstr, which has improved quite a bit in the last year or so. There's a paper on my home page about it (Constructor specialization for Haskell). Perhaps we should review the documentation you point to! Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
On 7/17/07, Martin Coxall [EMAIL PROTECTED] wrote: Me too, which is why I find your statement that expertise in C++ is easy to acquire. Seeing some of my colleagues' code is enough to tell me that this is most definitely not the case. You're quite right. That was careless on my part. Though the way C++ is taught at the undergraduate level, and the way it is perceived by the inexperienced is that it isn't so hard. But then again, I've taught Java at the ugrad level, and what do I know about Java, other that it'd be quite a nice place to have a holiday some time :) T. -- Dr Thomas Conway [EMAIL PROTECTED] Silence is the perfectest herald of joy: I were but little happy, if I could say how much. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Practise fingerspelling with Haskell! (Code cleanup request)
The following is a slap-dash program for generating a list of pairs of words which differ by, at most, one letter. It's quite verbose at the moment, because (a) that was the way I wrote it, a snippet at a time, and (b) I lack the wit to make it shorter. Can anyone recommend ways to make this program more efficient/neat/elegant? It runs in decent time on my machine, but it's not exceedingly pretty and I'm sure it can be made shorter too. (The full thing can be found at http://193.219.108.225/code/fingerspell/ if you want to pull in a working version to play with. The purpose of the program is for a game to practise fingerspelling when learning sign language. More on that here: http://brokenhut.livejournal.com/265471.html.) Cheers, D. edited highlights below -- Number of letters difference between two words. difference :: Pair - Int difference = length . filter (==False) . uncurry (zipWith (==)) -- Keep only pairs that differ by at most -- one letter difference. keepOneDiff :: PairSet - PairSet keepOneDiff = map snd . filter (\x - (fst x) 2) . map (difference id) -- Pairs of words of equal length, sorted to reduce -- duplicates of (a,b), (b,a) type. They shouldn't -- be completely eradicated because part of the game -- is to spot when they;re the same word. listPairs :: WordSet - PairSet listPairs ws = [ (w, w') | w - ws, w' - ws, length w == length w', w = w' ] -- Take N pairs of words which are the same -- length and differ by at most one letter. wordpairs :: Int - WordSet - PairSet wordpairs n = take n . keepOneDiff . listPairs fingerspell wl p = do wordfile - words `liftM` readFile /usr/share/dict/words mapM_ pretty $ wordpairs p $ filter (requirements) wordfile -- Make sure all the words are of the required length and are -- just made up of letters, not punctuation. where requirements w = length w == wl all (isAlpha) w pretty (x,y) = putStrLn $ x ++ , ++ y ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
On Tue, Jul 17, 2007 at 19:43:51 +1000, Thomas Conway wrote: On 7/17/07, Martin Coxall [EMAIL PROTECTED] wrote: Me too, which is why I find your statement that expertise in C++ is easy to acquire. Seeing some of my colleagues' code is enough to tell me that this is most definitely not the case. You're quite right. That was careless on my part. Though the way C++ is taught at the undergraduate level, and the way it is perceived by the inexperienced is that it isn't so hard. But then again, I've taught Java at the ugrad level, and what do I know about Java, other that it'd be quite a nice place to have a holiday some time :) My wife is from Java so if you need some advice on good vacation spots I'd be happy to ask her advice ;-) /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) [EMAIL PROTECTED] Jabber: [EMAIL PROTECTED] http://therning.org/magnus pgpktMsNwDJFq.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
On 7/17/07, Magnus Therning [EMAIL PROTECTED] wrote: On Tue, Jul 17, 2007 at 19:43:51 +1000, Thomas Conway wrote: On 7/17/07, Martin Coxall [EMAIL PROTECTED] wrote: Me too, which is why I find your statement that expertise in C++ is easy to acquire. Seeing some of my colleagues' code is enough to tell me that this is most definitely not the case. You're quite right. That was careless on my part. Though the way C++ is taught at the undergraduate level, and the way it is perceived by the inexperienced is that it isn't so hard. But then again, I've taught Java at the ugrad level, and what do I know about Java, other that it'd be quite a nice place to have a holiday some time :) My wife is from Java so if you need some advice on good vacation spots I'd be happy to ask her advice ;-) import java.wife.advice.CheapHotels; ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: xkcd #287 NP-Complete
Hugh Perkins wrote: Your solution looks really elegant, and runs insanely fast. Can you explain how it works? I will jump in and explain, using a more finely named version: xkcd_c287' = foldr (\cost without - let (poor, rich) = splitAt cost without with = poor ++ zipWith (++) rich using_cost using cost = (map (add_cost) with) where add_cost xs = cost:xs in with) ([[]] : repeat []) [215, 275, 335, 355, 420, 580] -- [2, 4, 150001] !! 1505 -- 150005 At the top level it uses (!!) to pick the 1505th element of the list produced by the use of foldr. foldr function to combine new value with previous result seed result list of new values Here the list of new values is the list of item prices (in pennies) from the menu. The seed result is the answer in the absence of anything on the menu. The seed is ([[]] : repeat []) which is a list of (list of prices). The n th member of the outer list holds the solution for a price of n pennies. Thus the (!! 1505) selects the answer for a target price of $15.05. The seed result has an empty list in the 0th position since ordering nothing is a solution to a target price of $0.00. The function works as follows: (\cost without - The 'cost' is the price of the new item on the menu. The 'without' is the answer taking into account all previously processed items on the menu (before the 'cost' item). The result will be a new answer taking into account 'cost' as well. let (poor, rich) = splitAt cost without The items in the old answer 'without' before the index 'cost' are solutions for a target price cheaper than 'cost' and these are in the 'poor' list. These answers are unchanged by the addition of the 'cost' item. The items in the 'rich' part of the answer may get new solutions that include ordering the new 'cost' item. with = poor ++ zipWith (++) rich using_cost using cost = (map add_cost with) where add_cost xs = cost:xs in with) The new answer will be 'with' which is defined recursively. The first elements of 'with' are the 'poor' parts of the old answer 'without' that are obviously unchanged. The 'zipWith (++) rich using_cost' combines the previous 'rich' answers without 'cost' with a new list that uses the 'cost' item. This is: using cost = (map add_cost with) where add_cost xs = cost:xs The using_cost list is made from taking the list of answers and prepending the 'cost' item to all the solutions. If this were applied to 'without' instead of 'with'... using cost = (map add_cost without) where add_cost xs = cost:xs ...then the definition of 'with' would not be recursive and would allow for solutions that only order each menu item 0 or 1 times. Since the definition of using_cost does apply the map to 'with' it can add_cost to answers that already have has add_cost applied to them. Thus it finds all answers that order the menu items 0,1,2,3.. arbitrarily many times. The n th item in 'with' or 'without' has total price of n, and after add_cost it has a total price of cost+n, and must be in the (cost+n)th position in the answer 'with'. This is achieve by the using_cost items being after the (poor ++) which means they have been shifted by (length poor) positions which, by the definition of (splitN cost), is equal to 'cost'. Cheers, Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Mux, was Re: Clearly, Haskell is ill-founded
On 16 Jul 2007, at 19:53, Stefan Holdermans wrote:
I wrote:
I came up with [...]
apfelmus' solution is of course more elegant, but I guess it boils
down to the same basic idea.
Yep, you need inductive data to guarantee that you eventually stop
spitting out one sort of thing and flip over to the other. Here's my
version.
Mux...
data{-codata-} Mux x y = Mux (Muy x y)
...is defined by mutual induction with...
data Muy x y = y :- Muy x y | x :~ Mux y x
...which guarantees that we will get more x, despite the odd y
in the way. It's inductively defined, so we can't (y :-) forever;
we must eventually (x :~), then flip over. So,
demuxL :: Mux x y - Stream x
demuxL (Mux muy) =
let (x, mux) = skipper muy
in x : demuxR mux
is productive, given this helper function
skipper :: Muy x y - (x, Mux y x)
skipper (y :- muy) = skipper muy
skipper (x :~ mux) = (x, mux)
which is just plain structural recursion. Once we've got out x,
we carry on with a Mux y x, flipping round the obligation to
ensure that we don't stick with x forever. To carry on getting
xs out...
demuxR :: Mux y x - Stream x
demuxR (Mux (x :- muy)) = x : demuxR (Mux muy)
demuxR (Mux (y :~ mux)) = demuxL mux
...just pass them as they come, then flip back when the y arrives.
Apfelmus, thanks for
| Or rather, one should require that the observation
|
| observe :: Mux x y - Stream (Either x y)
|
| respects consL and consR:
|
| observe . consL x = (Left x :)
| observe . consR y = (Right y :)
which is a very nice way to clean up my waffly spec.
I rather like this peculiar world of mixed coinductive and inductive
definitions. I haven't really got a feel for it yet, but I'm glad I've
been introduced to its rich sources of amusement and distraction, as
well as its potential utility. (My colleague, Peter Hancock, is the
culprit; also the man with the plan. For more, google
Peter Hancock eating streams
and poke about.)
Cheers for now
Conor
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] F#
Has anyone tried out F#? Is this a taboo subject here? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] -O2 compile option can give speed increase over -O. Fasta shootout program test runs.
Derek Elkins wrote: Just to add as this was not addressed. -O2 -does not- turn off bounds checking or any other obvious safety mechanism. although even just -O removes GHC's special 'assert'ions (unless you explicitly keep them on?) -- though they shouldn't be used in such a way that they could trigger, assuming that the code/library that employs them is non-buggy (or exports 'unsafe' things in which case a library's client also has to be non-buggy). Bounds checking is turned off iff you use functions named like unsafeAt, regardless of -O0, -O2 or any other optimization flags :) Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] F#
I've been meaning to tackle F# as my ML of choice (seeing as I'll need to get comfortable with .Net, I may as well hit two birds with one stone). I've been waiting for the text /Expert F#/ to come out, as it looks /Foundations of F#/ is pitched towards someone learning their first functional language. On 7/17/07, Edward Ing [EMAIL PROTECTED] wrote: Has anyone tried out F#? Is this a taboo subject here? ___ 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] GHC 6.6.1: Where is Graphics.SOE ?
I am trying to use Graphics.SOE (that was present at least in GHC 6.4) to go through Simple Graphics examples as described in Pail Hudak book The Haskell School of Expression. Learning functional programming through multimedia. It looks like Graphics.SOE does not anymore exist in GHC 6.6.1. Where one can get it or what to use instead of it? Do I understand right that Graphics library in GHC 6.6.1 is split between OpenGL and GLUT modules? Any tutorials on OpenGL and GLUT modules similar to Paul Hudak Simple Graphics? Thanks! -- Dmitri O. Kondratiev [EMAIL PROTECTED] http://www.geocities.com/dkondr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Getting lambdabot to work with 6.6.1
Dear, After a suggestion from quicksilver, I decided to write this message. To get lambdabot working on 6.6.1 you need to: 1) ensure you have the regexp-base, regexp-compat and regexp-posix from hackage installed 2) If you install them from user, make sure to add --user in the build-script of lambdabot 3) Get hs-plugins from darcs http://www.cse.unsw.edu.au/~dons/code/hs-plugins/, not from hackage (Lemmih informed it's an issue with the .hi parser) 4) Fix Lib/Parser.hs and replace 606 with = 606 in the #if GLASSGOW_HASKELL around the definition of pling_name and co 5) Remove the Maybe-definition of arbitrary in scripts/ShowQ.hs 6) Make sure to uncomment the runplugs section in lambdabot.cabal 7) ... 8) Profit Cheers ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mux, was Re: Clearly, Haskell is ill-founded
On Tue, 2007-07-17 at 13:23 +0100, Conor McBride wrote:
On 16 Jul 2007, at 19:53, Stefan Holdermans wrote:
I wrote:
I came up with [...]
apfelmus' solution is of course more elegant, but I guess it boils
down to the same basic idea.
Yep, you need inductive data to guarantee that you eventually stop
spitting out one sort of thing and flip over to the other. Here's my
version.
Mux...
data{-codata-} Mux x y = Mux (Muy x y)
...is defined by mutual induction with...
data Muy x y = y :- Muy x y | x :~ Mux y x
As an inductive data type, isn't this empty?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does Data.Map exist when...
Tony Morris wrote: ...it seems to be a special case of Set? Does Data.Map add anything more useful than Map' below? Besides technical differences, beware that mere convenience makes or breaks success of tools (languages, libraries). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Ann: Emping 0.3
Hello All, Version 0.3 of Emping is available. Emping is a utility that reads a table in a csv (comma separated) format that can be generated from Open Office Calc (spreadsheet), derives all shortest rules for a selected attribute, and writes them to a .csv file that can be read by OO Calc. The shortest rules may be partially ordered by implication (entailment) and equivalence (equality) and the top level is also shown in .csv format. Optionally all logical entailments and equalities are listed as well. If the data set contains ambiguous rules or more occurrences of the same rule, the user is warned. The main difference with V0.2 is that v0.3 can now handle intermediate size files (100 to a few thousand rules) because the transformation of conjunctive form (ands of ors) to disjunctive (ors of ands), which seemed to be exponential in the number of rules, has been optimized by using an intermediate 'maybe tree'. Probably I also used the wrong fold, without strictness, in the prior version, but it would still have been exponential. I 'think' it's now closer to linear to the number of rules, and quadratic to the number of attributes. But tests show the completion time is highly dependent on how well the data is structured. Obviously, much has still to be done. More info, for those who are interested, on http://j-van-thiel.speedlinq.nl/emp/empug.html Thank you, Hans van Thiel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC 6.6.1: Where is Graphics.SOE ?
Dmitri O.Kondratiev: It looks like Graphics.SOE does not anymore exist in GHC 6.6.1. Where one can get it or what to use instead of it? You may try Gtk2Hs, which includes an implementation of SOE, called Graphics.SOE.Gtk. (It works independently of the actual Gtk API.) Use then the darcs version, because I remember an SOE bug fixed since the last release. Malte ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell shootout game
Hugh Perkins wrote: Had an idea: a real shootout game for Haskell. The way it would work is: - you email a haskell program to a specific address - it shows up on a web-page The webpage shows the last submitted solution for each person - anyone can select two solutions and click Fight - the scripts fight in an arena for a second or so, and the results are published to the website ... Something like this was done as a student project at Chalmers a few years ago. Unfortunately the web site is gone, but some of it survives in the Wayback machine: http://web.archive.org/web/20040811042735/www.dtek.chalmers.se/~d00nibro/hwars/index.php4?Page=presentation You can probably find out more if you ask the project members: http://web.archive.org/web/20040811042126/www.dtek.chalmers.se/~d00nibro/hwars/index.php4?Page=members /Björn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: External Sort and unsafeInterleaveIO
Ben wrote:
a haskell newbie here, searching for comments and wisdom on my code.
i had a project to try to implement external sort in haskell as a
learning exercise. (external sort is sorting a list that is too large
to fit in main memory, by sorting in chunks, spooling to disk, and
then merging. more properly there probably should be multiple stages,
but for simplicity i'm doing a one-stage external sort.)
i'd appreciate any testing, comments and suggestions from the haskell
gods out there.
I'm not a god but I like it very much :) Especially because it's
laziness in action.
blocks - mapM (\x - do {bs - hGetContentsWithCursor h x;
return $ Bin.decode bs}) idx
(Minuscule cosmetics:
blocks - mapM ((liftM Bin.decode) . hGetContentsWithCursor h) idx
)
Merging chunks. K-way merge (and in fact external sort in general) is
detailed in Knuth, where he recommends tournament trees. The easiest
thing is to probably use one of Okasaki's heaps. I'll use splay
heaps, because I don't know any better.
It would be better if I changed Ord for blocks to only check the first
element.
kMerge :: (Ord a) = [[a]] - [a]
kMerge [] = []
kMerge l =
let h = Splay.fromSeq l in
kM (Splay.minElem h) (Splay.deleteMin h)
where
kM :: (Ord a) = [a] - Splay.Heap [a] - [a]
kM l h
| h == Splay.empty = l
| otherwise =
let next = Splay.minElem h
(f, b) = span (\x - x = head next) l
in
f ++ (kM next (if null b then Splay.deleteMin h
else (Splay.insert b $ Splay.deleteMin h)))
kMergeSort :: (Ord a) = [a] - [a]
kMergeSort l = kMerge $ blockify blocksize l
Oh, I would have expected a lazy mergesort here. Internally, this will
work like a tournament heap. See also
http://article.gmane.org/gmane.comp.lang.haskell.cafe/24180
Regards,
apfelmus
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Is this haskelly enough?
Hi, As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http://www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind enough to cast their eye over my code? I get the feeling there's a better way of doing it! subarrays :: [a] - [[a]] subarrays [] = [[]] subarrays xs = (sa xs) ++ subarrays (tail xs) where sa xs = [ys | n - [1..length xs], ys - [(take n xs)]] maxsubarrays :: [Integer] - [Integer] maxsubarrays xs = msa [] (subarrays xs) where msa m [] = m msa m (x:xs) | sum x sum m = msa x xs | otherwise = msa m xs --for testing: should return [2, 5, -1, 3] main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1] I've read tutorials about the syntax of Haskell, but I can't seem to find any that teach you how to really think in a Haskell way. Is there anything (books, online tutorials, exercises) that anyone could recommend? Thanks, James ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
I've read tutorials about the syntax of Haskell, but I can't seem to find any that teach you how to really think in a Haskell way. Is there anything (books, online tutorials, exercises) that anyone could recommend? the book The Haskell School of Expression is a good printed resource in this regard one thing i like about haskell is that it the tools are very clear about enforcing many semantic elements of the language. for example, you won't have to think too much about the haskell way of doing i/o - its enforced. on the other hand, you *do* have the choice as to the degree to which you want to engage the type system, and that for me continues to be a challenge coming from a duck type world of perl for nearly a decade. i admit i started in haskell throwing strings around and even wanting to regex them to extract meaning. all perfectly legit in haskell but not really exploiting the strength of the type system to aid in the development of robust and elegant programs. to me that is the biggest challenge to thinking in a haskell way - thinking typefully. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
On Jul 17, 2007, at 22:26 , James Hunt wrote: Hi, As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http:// www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind enough to cast their eye over my code? I get the feeling there's a better way of doing it! subarrays :: [a] - [[a]] subarrays [] = [[]] subarrays xs = (sa xs) ++ subarrays (tail xs) where sa xs = [ys | n - [1..length xs], ys - [(take n xs)]] maxsubarrays :: [Integer] - [Integer] maxsubarrays xs = msa [] (subarrays xs) where msa m [] = m msa m (x:xs) | sum x sum m = msa x xs | otherwise = msa m xs --for testing: should return [2, 5, -1, 3] main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1] I've read tutorials about the syntax of Haskell, but I can't seem to find any that teach you how to really think in a Haskell way. Is there anything (books, online tutorials, exercises) that anyone could recommend? Thanks, James Hi james, here's one solution: import Data.List maxsubarrays xs = maximumBy (\x y - sum x `compare` sum y) [zs | ys - inits xs, zs - tails ys] This can be made somewhat nicer with 'on': import Data.List maxsubarrays xs = maximumBy (compare `on` sum) [zs | ys - inits xs, zs - tails ys] on, which will appear in Data.Function in the next release of base, is defined thusly: on :: (b - b - c) - (a - b) - a - a - c (*) `on` f = \x y - f x * f y /Björn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
On 7/17/07, James Hunt [EMAIL PROTECTED] wrote: As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http://www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind enough to cast their eye over my code? I get the feeling there's a better way of doing it! subarrays :: [a] - [[a]] subarrays [] = [[]] subarrays xs = (sa xs) ++ subarrays (tail xs) where sa xs = [ys | n - [1..length xs], ys - [(take n xs)]] Check out the functions in Data.List inits :: [a] - [[a]] tails :: [a] - [[a]] also, in a list comprehension, rather than: ys - [x] consider: let ys = x in this specific case: [take n xs | n - [1..length xs]] would be even better (though using inits and tails to accomplish this would be best of all) maxsubarrays :: [Integer] - [Integer] maxsubarrays xs = msa [] (subarrays xs) where msa m [] = m msa m (x:xs) | sum x sum m = msa x xs | otherwise = msa m xs --for testing: should return [2, 5, -1, 3] main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1] This problem lends itself to being solved with Dynamic Programming and can be solved in a single pass of the input list. (Rather than supply the answer I'll encourage you to seek it out) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
Hi James. I would be tempted to write this a little differently than you did. First, some of the pieces you've written have equivalents in the standard library; there's no harm in rewriting them, but I figured I'd point out that they're there. (Hoogle - haskell.org/hoogle, I believe - can be a good way to find these.) Second, I've rewritten it using function composition. To me, this makes the combination of different components more obvoius - like the pipe in Unix. So, code: import Data.List -- I believe this is scheduled for inclusion in the standard library; -- I find it very useful f `on` g = \x y - f (g x) (g y) -- We can find the maximum sublist by comparing the sums -- of each sublist. maxsl = maximumBy (compare `on` sum) . sublists -- the tails function returns each tail of the given list; the inits function -- is similar. By mapping inits over tails, we get all the sublists. where sublists = filter (not . null) . concatMap inits . tails That works for your test case; I haven't tried it exhaustively. /g On 7/17/07, James Hunt [EMAIL PROTECTED] wrote: Hi, As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http://www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind enough to cast their eye over my code? I get the feeling there's a better way of doing it! subarrays :: [a] - [[a]] subarrays [] = [[]] subarrays xs = (sa xs) ++ subarrays (tail xs) where sa xs = [ys | n - [1..length xs], ys - [(take n xs)]] maxsubarrays :: [Integer] - [Integer] maxsubarrays xs = msa [] (subarrays xs) where msa m [] = m msa m (x:xs) | sum x sum m = msa x xs | otherwise = msa m xs --for testing: should return [2, 5, -1, 3] main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1] I've read tutorials about the syntax of Haskell, but I can't seem to find any that teach you how to really think in a Haskell way. Is there anything (books, online tutorials, exercises) that anyone could recommend? Thanks, James ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- The man who'd introduced them didn't much like either of them, though he acted as if he did, anxious as he was to preserve good relations at all times. One never knew, after all, now did one now did one now did one. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
You hardly ever need to use explicit recursion in Haskell. Every useful way of doing recursion has already been captured in some higher order function. For example here is your subarrays implemented using unfoldr: subarrays xs = concat $ unfoldr f xs where f [] = Nothing f xs = Just ( [ys | n - [1..length xs], ys - [(take n xs)]], tail xs) On Jul 17, 2007, at 4:26 PM, James Hunt wrote: Hi, As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http:// www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind enough to cast their eye over my code? I get the feeling there's a better way of doing it! subarrays :: [a] - [[a]] subarrays [] = [[]] subarrays xs = (sa xs) ++ subarrays (tail xs) where sa xs = [ys | n - [1..length xs], ys - [(take n xs)]] maxsubarrays :: [Integer] - [Integer] maxsubarrays xs = msa [] (subarrays xs) where msa m [] = m msa m (x:xs) | sum x sum m = msa x xs | otherwise = msa m xs --for testing: should return [2, 5, -1, 3] main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1] I've read tutorials about the syntax of Haskell, but I can't seem to find any that teach you how to really think in a Haskell way. Is there anything (books, online tutorials, exercises) that anyone could recommend? Thanks, James ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ (---o---o-o-o---o-o-o( David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
James, In my earlier post I mentioned that you should find a dynamic programming approach to this problem. My solution is presented below, so you've been warned if you are still working this out: === READ ABOVE === import Data.List (foldl') solve = snd . foldl' aux (0, 0) where aux (cur, best) x = (max 0 cur', max best cur') where cur' = cur + x -- Eric Mertens ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Clearly, Haskell is ill-founded
Conor McBride wrote: Hi all On 9 Jul 2007, at 06:42, Thomas Conway wrote: I don't know if you saw the following linked off /. http://www.itwire.com.au/content/view/13339/53/ [..] The basic claim appears to be that discrete mathematics is a bad foundation for computer science. I suspect the subscribers to this list would beg to disagree. It's true that some systems are better characterised as corecursive coprograms, rather than as recursive programs. This is not a popular or well-understood distinction. In my career as an advocate for total programming (in some carefully delineated fragment of a language) I have many times been gotcha'ed thus: but an operating system is a program which isn't supposed to terminate. No, an operating system is supposed to remain responsive. And that's what total coprograms do. I like that distinction.. how is shutting down or executing (switching to) another arbitrary OS's kernel modeled (in response to input, in a total way, of course)? Even so, I'd say that it's worth raising awareness of it. Haskell's identification of inductive data with coinductive data, however well motivated, has allowed people to be lazy. People aren't so likely to be thinking do I mean inductive or coinductive here?, is this function productive? etc. The usual style is to write as if everything is inductive, and if it still works on infinite data, to pat ourselves on the back for using Haskell rather than ML. I'm certainly guilty of that. I'd go as far as to suggest that codata be made a keyword, at present doubling for data, but with the documentary purpose of indicating that a different mode of (co)programming is in order. It might also be the basis of better warnings, optimisations, etc. Moreover, it becomes a necessary distinction if we ever need to identify a total fragment of Haskell. Overkill, perhaps, but I often find it's something I want to express. I find that one of Haskell's faults is it's too hard to avoid the everything is lazy even when I want to - partly because I don't understand inductive vs. coinductive very well (particularly, not in practice). If data List a = Nil | Cons a (List a) is finite and codata Stream a = Cons a (Stream a) is infinite, what is codata CoList a = Nil | Cons a (CoList a)? I need a tutorial on more-total programming in Haskell =) (leading to a keener awareness of just where the untamed laziness of Haskell can occasionally make code much more concise and understandable, and where the laziness actually has a formal structure that one can stay within) Non-inductive, finite structures - cyclic directed graphs, usually - are quite annoying to implement and use in Haskell. (Especially if you want garbage collection and sharing to work well with them... or if different nodes should be different types, only allowed in particular arrangements - I'm pretty sure that dependent types would alleviate that last one, not sure about the other irritations ) Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: haskell for web
On 7/17/07, Martin Coxall [EMAIL PROTECTED] wrote: I wonder why 'we' aren't pushing things like this big time. When Ruby took off, more than anything else it was because of Rails. Web programming is something 'the kids' can really get into, and it caused Ruby to explode into the mainstream geek consciousness. Maybe the Haskell community should push something like Happs or Wash in the same way. I'm gonna agree with this. Web applications are really easy to write, and easy to publish, searchable in Google etc. It's also a big business requirement. The difference in value between a script that does something fancy, and a webpage that does something less fancy, but is easy to use, is enormous. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
On 7/17/07, Thomas Conway [EMAIL PROTECTED] wrote: And this is where I think Haskell has it all over C++, Java, and the rest. Haskell is easy to learn at a simple level, and hard to learn at the expert level, but once learned is very powerful and has excellent payoffs in terms of productivity. With C++ or Java, the expertise is somewhat easier to acquire, but you never get the payoff. And before you all flame, yes, I do know C++ at an expert level, and that is exactly why, after 7 years of writing server software in C++, I now want to do it in Haskell. You know, it just occurred to me: I get the feeling that many Haskell programmers are ex-C++ programmers, which makes a certain amount of sense because C++ is insanely hard to debug and maintain, because of stack/heap corruption, and lack of a GC. Am I the only person who finds it interesting/worrying that there are few to no people in the group who are ex-C# programmers. I mean, you could argue that C# programmers are simply too stupid to do Haskell, but ... you know, there is another explanation ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
On 7/18/07, Hugh Perkins [EMAIL PROTECTED] wrote: Am I the only person who finds it interesting/worrying that there are few to no people in the group who are ex-C# programmers. I mean, you could argue that C# programmers are simply too stupid to do Haskell, but ... you know, there is another explanation ;-) I wouldn't say too stupid, but it may be a cultural thing. People working in C++ are more likely to be doing what I would call technical programming, and correspondingly more likely to be interested in Haskell, and to appreciate what it has to offer from painful personal experience. From what I know of the marketplace, people working in C# are more likely to be doing client/integration work where technical finesse is less important, and are therefore less likely to see the point. cheers, T. -- Dr Thomas Conway [EMAIL PROTECTED] Silence is the perfectest herald of joy: I were but little happy, if I could say how much. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: haskell for web
On 7/18/07, brad clawsie [EMAIL PROTECTED] wrote: i have wondered what it would take to get a mod_haskell for apache If you make a mod_haskell, please make sure it's secure. It's insanely hard to convince web hosting companies to add support for new mod_myfavoritelanguagehere. If the mod is secure and easy to install and maintain, that task becomes orders of magnitude easier. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] F#
On Tuesday 17 July 2007 14:53:20 Edward Ing wrote: Has anyone tried out F#? Yes. We've been using F# for 9 months now and have several products written in it. Is this a taboo subject here? Probably. ;-) -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: haskell for web
On Wed, Jul 18, 2007 at 12:35:23AM +0200, Hugh Perkins wrote: If you make a mod_haskell, please make sure it's secure. It's insanely hard to convince web hosting companies to add support for new mod_myfavoritelanguagehere. i personally don't have any plans on creating mod_haskell, it is beyond my skillset and time allowance. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
[EMAIL PROTECTED]:~/ProjectRepos/learning$ ghc -fglasgow-exts -e 'main' maxSubArrays.hs should be [2,5,-1,3]: [2,5,-1,3] [EMAIL PROTECTED]:~/ProjectRepos/learning$ cat maxSubArrays.hs import Data.List -- maximum sub-array: [2, 5, -1, 3] main = do putStrLn $ should be ++ show [2, 5, -1, 3] ++ : putStrLn $ show $ maxsubarray [-1, 2, 5, -1, 3, -2, 1] maxsubarray :: forall a. (Ord [a], Ord a, Num a) = [a] - [a] maxsubarray a = head $ reverse $ sortBy comparelists $ sublists a comparelists l1 l2 = compare (sum l1) (sum l2) sublists a = nub $ sort $ concat $ map inits $ tails a [EMAIL PROTECTED]:~/ProjectRepos/learning$ cheers :) t. James Hunt [EMAIL PROTECTED] Sent by: [EMAIL PROTECTED] 07/17/2007 04:26 PM To haskell-cafe@haskell.org cc Subject [Haskell-cafe] Is this haskelly enough? Hi, As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http://www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind enough to cast their eye over my code? I get the feeling there's a better way of doing it! subarrays :: [a] - [[a]] subarrays [] = [[]] subarrays xs = (sa xs) ++ subarrays (tail xs) where sa xs = [ys | n - [1..length xs], ys - [(take n xs)]] maxsubarrays :: [Integer] - [Integer] maxsubarrays xs = msa [] (subarrays xs) where msa m [] = m msa m (x:xs) | sum x sum m = msa x xs | otherwise = msa m xs --for testing: should return [2, 5, -1, 3] main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1] I've read tutorials about the syntax of Haskell, but I can't seem to find any that teach you how to really think in a Haskell way. Is there anything (books, online tutorials, exercises) that anyone could recommend? Thanks, James ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe --- 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
Re: [Haskell-cafe] Is this haskelly enough?
Bjorn Bringert wrote: import Data.List maxsubarrays xs = maximumBy (compare `on` sum) [zs | ys - inits xs, zs - tails ys] I love this solution: simple, understandable, elegant. As a nit, I might take out the ys and zs names, which obscure the fact that there is a hidden symmetry in the problem: maxsubarrays xs = pickBest (return xs = inits = tails) where pickBest = maximumBy (compare `on` sum) -- NOTE: Since pickBest is invariant under permutation of its arg, -- the order of inits and tails above may be reversed. Dan Weston ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: haskell for web
On Wed, Jul 18, 2007 at 12:17:12AM +0200, Hugh Perkins wrote: On 7/17/07, Martin Coxall [EMAIL PROTECTED] wrote: I wonder why 'we' aren't pushing things like this big time. When Ruby took off, more than anything else it was because of Rails. i agree that web programming is a domain that cannot be ignored i have wondered what it would take to get a mod_haskell for apache wash looks interesting, but very few companies and isps are going to run a niche fastcgi platform (even those already running rails). apache is still the de facto open serving platform. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Getting lambdabot to work with 6.6.1
I also commented out arrows as a dependency in the .cabal, I think. Was that not a good idea? it seemed to work. Shachaf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: haskell for web
On Jul 18, 2007, at 0:27 , brad clawsie wrote: On Wed, Jul 18, 2007 at 12:17:12AM +0200, Hugh Perkins wrote: On 7/17/07, Martin Coxall [EMAIL PROTECTED] wrote: I wonder why 'we' aren't pushing things like this big time. When Ruby took off, more than anything else it was because of Rails. i agree that web programming is a domain that cannot be ignored i have wondered what it would take to get a mod_haskell for apache wash looks interesting, but very few companies and isps are going to run a niche fastcgi platform (even those already running rails). apache is still the de facto open serving platform. If you use Network.FastCGI, and compile (linking statically is a good idea as well) on your own machine, you can run Haskell code on any web host that supports FastCGI. That's what I do with Hope, http:// hope.bringert.net/ /Björn___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
on, which will appear in Data.Function in the next release of base, is defined thusly: on :: (b - b - c) - (a - b) - a - a - c (*) `on` f = \x y - f x * f y You can also use Data.Ord.comparing, in this case -- comparing is just (compare `on`). From Ord.hs: -- | -- comparing p x y = compare (p x) (p y) -- -- Useful combinator for use in conjunction with the @xxxBy@ family -- of functions from Data.List, for example: -- --... sortBy (comparing fst) ... comparing :: (Ord a) = (b - a) - b - b - Ordering comparing p x y = compare (p x) (p y) Shachaf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
Nicest. I think your definition has reached nirvana. I think a good haskell-cafe thread is like a Shakespeare play. People at every level of experience can get something from it. The early replies answer the question, with follow-on ones exploring the roads less traveled. I for one did not know how to construct the fully pointless version below, and if I hadn't asked, I doubt I ever would. I also learned of the list monad this exact same way, so I think its a good and gentle way to introduce people to it. Dan Bjorn Bringert wrote: On Jul 18, 2007, at 1:00 , Dan Weston wrote: Bjorn Bringert wrote: import Data.List maxsubarrays xs = maximumBy (compare `on` sum) [zs | ys - inits xs, zs - tails ys] I love this solution: simple, understandable, elegant. As a nit, I might take out the ys and zs names, which obscure the fact that there is a hidden symmetry in the problem: maxsubarrays xs = pickBest (return xs = inits = tails) where pickBest = maximumBy (compare `on` sum) -- NOTE: Since pickBest is invariant under permutation of its arg, -- the order of inits and tails above may be reversed. Dan Weston Nice. Here's a pointless version: maxsubarrays = maximumBy (compare `on` sum) . (= tails) . inits Though I avoided using the list monad in the first solution, since I thought it would make the code less understandable for a beginner. /Björn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
On Tuesday 17 July 2007 23:26:08 Hugh Perkins wrote: Am I the only person who finds it interesting/worrying that there are few to no people in the group who are ex-C# programmers. I mean, you could argue that C# programmers are simply too stupid to do Haskell, but ... you know, there is another explanation ;-) To understand this, I think you must look at the number of technical users for each language. There are a huge number of technical C++ and Java programmers but a tiny number of technical C# programmers in comparison. The few technical C# programmers are migrating to F# because it is next door and F# programmers are better looking. You can find evidence of this simply by searching for mundane numerical libraries like Fast Fourier Transform (FFT) implementations. If you do this for C++ or Java you find hundreds of implementations, some of which will work. For OCaml, you find a handful of libraries all bundled with automated proofs of their correctness. When I did this for all .NET languages a couple of months ago, there was nothing worth having (even among expensive commercial solutions). So I wrote my own and productized it. Our FFT library in C# is an order of magnitude less popular than our technical libraries for OCaml but this is offset by the fact that people using C# have an order of magnitude more money. So I would say that the Haskell community can expect immigrants who are technical (or they wouldn't consider a fringe language) and that means they will be migrating primarily from C++ and Java. If you want to attract the maximum number of users then target your educational material at those people. The C++ programmers will know that coding to the metal is always essential and will demand proof that Haskell is as fast as C. They will also need to know how to unravel low-dimensional vector and matrix routines at compile time. The Java programmers will know that performance (particularly startup time) is completely irrelevant but being cross-platform and having extreme interoperability is pivotal. They will be particularly impressed by Haskell's brevity and the disappearance of some of Java's keywords like public, static, void and Factory. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
On Jul 17, 2007, at 7:10 PM, Bjorn Bringert wrote: Nice. Here's a pointless version: Good Freudian slip. maxsubarrays = maximumBy (compare `on` sum) . (= tails) . inits For the monadically-challenged, this is equivalent, yes-no? maxsubarrays = maximumBy (compare `on` sum) . concat . (map tails) . inits ___ (---o---o-o-o---o-o-o( David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
On Jul 18, 2007, at 1:00 , Dan Weston wrote: Bjorn Bringert wrote: import Data.List maxsubarrays xs = maximumBy (compare `on` sum) [zs | ys - inits xs, zs - tails ys] I love this solution: simple, understandable, elegant. As a nit, I might take out the ys and zs names, which obscure the fact that there is a hidden symmetry in the problem: maxsubarrays xs = pickBest (return xs = inits = tails) where pickBest = maximumBy (compare `on` sum) -- NOTE: Since pickBest is invariant under permutation of its arg, -- the order of inits and tails above may be reversed. Dan Weston Nice. Here's a pointless version: maxsubarrays = maximumBy (compare `on` sum) . (= tails) . inits Though I avoided using the list monad in the first solution, since I thought it would make the code less understandable for a beginner. /Björn___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
For the monadically-challenged, this is equivalent, yes-no? maxsubarrays = maximumBy (compare `on` sum) . concat . (map tails) . inits Or: maxsubarrays = maximumBy (compare `on` sum) . concatMap tails . inits (=) for lists is just (flip concatMap). Also, this is working with lists, not arrays -- maxsubarrays is probably a misleading name. Shachaf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] F#
| Has anyone tried out F#? | | Yes. We've been using F# for 9 months now and have several products | written in | it. | | Is this a taboo subject here? | Probably. ;-) Not at all! But there is a very active F# community that would be much more knowledgeable about F# than Haskell folk are likely to be. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
On Jul 17, 2007, at 22:26 , James Hunt wrote: As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http:// www.rubyquiz.com/quiz131.html) in Haskell. Haskell guru level: I am comfortable with higher order functions, but never think of using the list monad. Developing the answer went like this: - find all sublists - annotate each with its sum - find the best (sum, list) pair - throw away the sum best_sublist = snd . maximum . annotate_with_sums . all_sublists All sublists was easy: all_sublists = concatMap tails . inits Confession: the one mistake I made in this was using map here instead of concatMap, but the error message from Hugs was sufficiently clear. Annotating with sums is just doing something to each element, so annotate_with_sums = map (\xs - (sum xs, xs)) Put them together and you get best_sublist = snd . maximum . map (\xs - (sum xs, xs)) . concatMap tails . inits The trick here is that as far as getting a correct answer is concerned, we don't *care* whether we compare two lists with equal sums or not, either will do. To do without that trick, best_sublist = snd . maximumBy c . map s . concatMap tails . inits where s xs = (sum xs, xs) f (s1,_) (s2,_) = compare s1 s2 Confession: I actually made two mistakes. I remembered the inits and tails functions, but forgot to import List. Again, hugs caught this. However, the key point is that this is a TRICK QUESTION. What is the trick about it? This is a well known problem called The Maximum Segment Sum problem. It's described in a paper A note on a standard strategy for developing loop invariants and loops by David Gries (Science of Computer Programming 2(1984), pp 207-214). The Haskell code above finds each segment (and there are O(n**2) of them, at an average length of O(n) each) and computes the sums (again O(n) each). So the Haskell one-liner is O(n**3). But it CAN be done in O(n) time. Gries not only shows how, but shows how to go about it so that you don't have to be enormously clever to think of an algorithm like that. What would be a good exercise for functional programmers would be to implement the linear-time algorithm. The algorithm given by Gries traverses the array one element at a time from left to right, so it's not that hard. The tricky thing is modifying the algorithm to return the list; it might be simplest to just keep track of the end-points and do a take and a drop at the end. I think it is at least mildly interesting that people commented about things like whether to do it using explicit parameters (pointful style) or higher-order functions (pointless style) and whether to use the list monad or concatMap, but everyone seemed to be happy with a cubic time algorithm when there's a linear time one. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
On Wed, 2007-07-18 at 12:13 +1200, ok wrote: On Jul 17, 2007, at 22:26 , James Hunt wrote: As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http:// www.rubyquiz.com/quiz131.html) in Haskell. What is the trick about it? This is a well known problem called The Maximum Segment Sum problem. So well known that it is commonly used as an example in Haskell papers on calculating programs. I'm betting googling 'Maximum Segment Sum haskell' will find some of them. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
ok wrote: I think it is at least mildly interesting that people commented about things like whether to do it using explicit parameters (pointful style) or higher-order functions (pointless style) and whether to use the list monad or concatMap, but everyone seemed to be happy with a cubic time algorithm when there's a linear time one. Speaking only for myself, I concern myself with an algorithm when I am learning an algorithm, or using one to solve a real problem. I try out list monads to learn about list monads, because I am already comfortable with list comprehensions. I concern myself with syntax manipulations and pointedness for the sheer unadulterated fun of it. Then I go back to my day job using C++. Everyone has their own motivations. I would not draw any further conclusions about them from the data at hand. Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
On Wed, 2007-07-18 at 00:26 +0200, Hugh Perkins wrote: On 7/17/07, Thomas Conway [EMAIL PROTECTED] wrote: And this is where I think Haskell has it all over C++, Java, and the rest. Haskell is easy to learn at a simple level, and hard to learn at the expert level, but once learned is very powerful and has excellent payoffs in terms of productivity. With C++ or Java, the expertise is somewhat easier to acquire, but you never get the payoff. And before you all flame, yes, I do know C++ at an expert level, and that is exactly why, after 7 years of writing server software in C++, I now want to do it in Haskell. You know, it just occurred to me: I get the feeling that many Haskell programmers are ex-C++ programmers, which makes a certain amount of sense because C++ is insanely hard to debug and maintain, because of stack/heap corruption, and lack of a GC. Am I the only person who finds it interesting/worrying that there are few to no people in the group who are ex-C# programmers. I mean, you could argue that C# programmers are simply too stupid to do Haskell, but ... you know, there is another explanation ;-) Don't you think it's a little early for people to be abandoning C# en masse? For example, there are plenty of ex/current Java programmers. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Getting lambdabot to work with 6.6.1
syntactically.vincenz: Dear, After a suggestion from quicksilver, I decided to write this message. To get lambdabot working on 6.6.1 you need to: 1) ensure you have the regexp-base, regexp-compat and regexp-posix from hackage installed The .cabal file now enforces this. 2) If you install them from user, make sure to add --user in the build-script of lambdabot 3) Get hs-plugins from darcs [1]http://www.cse.unsw.edu.au/~dons/code/hs-plugins/ , not from hackage (Lemmih informed it's an issue with the .hi parser) quite so. 4) Fix Lib/Parser.hs and replace 606 with = 606 in the #if GLASSGOW_HASKELL around the definition of pling_name and co Send a patch. 5) Remove the Maybe-definition of arbitrary in scripts/ShowQ.hs Oh, that's changed in QuickCheck (yet another API change in 6.6.1!). Send a cpp patch. 6) Make sure to uncomment the runplugs section in lambdabot.cabal User the lambdabot.cabal.plugins file. 7) ... 8) Profit Cheers Good. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Getting lambdabot to work with 6.6.1
shachaf: I also commented out arrows as a dependency in the .cabal, I think. Was that not a good idea? it seemed to work. You just won't be able to use arrows transformers and other fun things in @eval. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Is this haskelly enough? -- errm but every answer is wrong(?)
(Or at least the problem is under-specified.) 1. There may be several sub-sequences having the maximum sum. So the type for the solution should be :: Num a = [a] - [[a]] (Note that the problem didn't ask for the maximum itself.) 2. The inits . tails approach adds a fault: It introduces a sprinkling of empty sub-sequences. These have sum zero. So in case the input list is all negative numbers ... Being a software tester for my day job, I looked first not for an elegant and/or efficient solution; but for where to stretch the boundaries of the problem. However, the key point is that this is a TRICK QUESTION. snip ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough? -- errm but every answer is wrong(?)
Correct, efficient, elegant: you can only have two out of three. I see where your priorities lie! :) Dan Anthony Clayden wrote: (Or at least the problem is under-specified.) 1. There may be several sub-sequences having the maximum sum. So the type for the solution should be :: Num a = [a] - [[a]] (Note that the problem didn't ask for the maximum itself.) 2. The inits . tails approach adds a fault: It introduces a sprinkling of empty sub-sequences. These have sum zero. So in case the input list is all negative numbers ... Being a software tester for my day job, I looked first not for an elegant and/or efficient solution; but for where to stretch the boundaries of the problem. However, the key point is that this is a TRICK QUESTION. snip ___ 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] Is this haskelly enough?
On Jul 17, 2007, at 7:10 PM, Bjorn Bringert wrote: maxsubarrays = maximumBy (compare `on` sum) . (= tails) . inits Though I avoided using the list monad in the first solution, since I thought it would make the code less understandable for a beginner. I felt uncomfortable seeing this. Let me see if I can explain why. Isn't the use of monads here unnecessary and obscure? The use of inits, tails and maximumBy ground the function to a list representation. There seems no hope of generalizing it to other monads. The use of = is just an obscure way of saying (flip concatMap). ___ (---o---o-o-o---o-o-o( David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 David F. Place wrote: The use of = is just an obscure way of saying (flip concatMap). Correction. The use of = is a more general way of saying (flip concatMap). Tony Morris http://tmorris.net/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGnXdcmnpgrYe6r60RAmKNAJ44OCBlQyBm7spV2+xFOeSFklXRggCfVlaj 95xIOWWAKinzyBMClorfkew= =lZRD -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Is this haskelly enough? -- errm but every answer is wrong(?)
On 2007-07-18, Anthony Clayden [EMAIL PROTECTED] wrote: (Or at least the problem is under-specified.) 2. The inits . tails approach adds a fault: It introduces a sprinkling of empty sub-sequences. These have sum zero. So in case the input list is all negative numbers ... Why is this a fault? The subsequence with maximum sum is then the empty subsequence. Perfectly accurate. -- Aaron Denney -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fwd: Happy Error
I'm forwarding this mail, in case anyone might know about the bug. -- Forwarded message -- From: Hugo Pacheco [EMAIL PROTECTED] Date: Jul 18, 2007 3:45 AM Subject: Happy Error To: [EMAIL PROTECTED] Hi Simon, I'm having what I supose ti be a oarsec internal error when trying to compile some grammar. I get: $ happy -g -a -c Parser.y happy: parE Is this a known bug? I could find no reference to it. I'm using happy version 1.16 and I can't reduce the problem to a single production. The grammar file is attached. Thanks in advance, hugo Parser.y Description: Binary data ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this haskelly enough? -- errm but every answer is wrong(?)
On 7/17/07, Anthony Clayden [EMAIL PROTECTED] wrote: 2. The inits . tails approach adds a fault: It introduces a sprinkling of empty sub-sequences. These have sum zero. So in case the input list is all negative numbers ... At least the concatMap inits . tails code that I posted also filtered empty lists to avoid this problem... it seems like a simple omission rather than a fault in the approach. /g -- The man who'd introduced them didn't much like either of them, though he acted as if he did, anxious as he was to preserve good relations at all times. One never knew, after all, now did one now did one now did one. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] External Sort and unsafeInterleaveIO
midfield:
hi folks --
a haskell newbie here, searching for comments and wisdom on my code.
i had a project to try to implement external sort in haskell as a
learning exercise. (external sort is sorting a list that is too large
to fit in main memory, by sorting in chunks, spooling to disk, and
then merging. more properly there probably should be multiple stages,
but for simplicity i'm doing a one-stage external sort.)
the trick is the number of files can quickly grow very large, so it is
best to use one large file and seek inside it around. however as one
can imagine the order-of-IO-operations becomes a bit tricky, if you're
seeking file handles around underneath Data.ByteString.Lazy's nose.
but late this night after not thinking about it for a while i had a
brainstorm: rewrite hGetContents to keep the handle position in the
right place! it's all about judicious use of unsafeInterleaveIO.
it seems to be rather fast, strangely faster than the usual sort at
times. it also seems to have nice memory characteristics, though not
perfect. it's hard to test because the normal sort function takes
too much RAM on large lists, making my computer swap like mad.
I have to agree with Mr. Apfelmus here. This is lovely code. It is exactly
what the ByteString team hoped people would be able to write
ByteStrings: Zen of Haskell code, where you win by working at a high
level, rather than a low level.
Thanks!
I've inserted some small comments though the source:
module ExternalSort where
Sort a list of Ords offline. We're doing this to be able to sort
things without taking up too much memory (for example sorting lists
too large to fit in RAM.) Laziness is imperative, as is the
order-of-operations.
import Control.Monad
import Data.List
import qualified Data.Binary as Bin
import qualified Data.ByteString.Lazy as B
import qualified Data.ByteString as P (hGetNonBlocking, null)
import Data.ByteString.Base (LazyByteString(LPS))
import Foreign.Storable (sizeOf)
import System.IO (openFile, hClose, hSeek, hTell, hIsEOF, hWaitForInput,
Handle, IOMode(ReadMode, WriteMode),
SeekMode(AbsoluteSeek))
import System.IO.Unsafe (unsafeInterleaveIO)
import qualified Data.Edison.Seq.ListSeq as LS
import qualified Data.Edison.Coll.SplayHeap as Splay
Conceptually, we sort a list in blocks, spool blocks to disk, then
merge back. However for IO performance it is better to read off
chunks of elements off the sorted blocks from disk instead of
elements-at-a-time.
It would be better if these were in KBytes instead of # of elements.
blocksize :: Int
blocksize = 1
Turn a list into a list of chunks.
slice :: Int - [a] - [[a]]
slice _ [] = []
slice size l = (take size l) : (slice size $ drop size l)
That's unnecessary parenthesis, and I'd probably use splitAt here:
myslice :: Int - [a] - [[a]]
myslice _ [] = []
myslice n xs = a : myslice n b where (a,b) = splitAt n xs
And just to check:
*M :m + Test.QuickCheck
*M Test.QuickCheck quickCheck (\n (xs :: [Int]) - n 0 == slice n xs ==
myslice n xs)
OK, passed 100 tests.
Turn a list into a list of blocks, each of which is sorted.
blockify :: (Ord a) = Int - [a] - [[a]]
blockify bsize l = map sort $ slice bsize l
Possibly you could drop the 'l' parameter:
blockify n = map sort . slice n
Serialize a block, returning the (absolute) position of the start.
dumpBlock :: (Ord a, Bin.Binary a) = Handle - [a] - IO Integer
dumpBlock h b = do
start - hTell h
B.hPut h $ Bin.encode b
return start
The actual sorting function. We blockify the list, turning it into a
list of sorted blocks, and spool to disk, keeping track of offsets.
We then read back the blocks (lazily!), and merge them.
externalSort [] = do return []
externalSort l = do
h - openFile ExternalSort.bin WriteMode
idx - mapM (\x - dumpBlock h x) (blockify blocksize l)
idx - mapM (dumpBlock h) (blockify blocksize l)
hClose h
h - openFile ExternalSort.bin ReadMode
blocks - mapM (\x - do {bs - hGetContentsWithCursor h x;
return $ Bin.decode bs}) idx
Possibly
forM idx $ \x - decode `fmap` hGetContentsWithCursor h x
return (kMerge $ blocks)
Merging chunks. K-way merge (and in fact external sort in general) is
detailed in Knuth, where he recommends tournament trees. The easiest
thing is to probably use one of Okasaki's heaps. I'll use splay
heaps, because I don't know any better.
It would be better if I changed Ord for blocks to only check the first
element.
kMerge :: (Ord a) = [[a]] - [a]
kMerge [] = []
kMerge l =
let h = Splay.fromSeq l in
kM (Splay.minElem h) (Splay.deleteMin h)
where
kM :: (Ord a) = [a] - Splay.Heap [a] - [a]
kM l h
| h == Splay.empty = l
| otherwise =
let next = Splay.minElem h
(f, b) = span (\x
[Haskell-cafe] Re: Happy Error
I'm sorry, it turned out to be pretty simples. The error appears when there are references to undefined terminal or non-terminal productions. That's it. Sorry for the messages, at least it might be of some help to someone else. hugo On 7/18/07, Hugo Pacheco [EMAIL PROTECTED] wrote: Hi Simon, I'm having what I supose ti be a oarsec internal error when trying to compile some grammar. I get: $ happy -g -a -c Parser.y happy: parE Is this a known bug? I could find no reference to it. I'm using happy version 1.16 and I can't reduce the problem to a single production. The grammar file is attached. Thanks in advance, hugo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] External Sort and unsafeInterleaveIO
hi -- thanks for the useful comments! i will definitely go through them carefully. unfortunately for this code (but fortunately for me) i defend my dissertation on monday so i'm a little distracted right now. i'm more than happy to donate this code or whatever improvements happen to it. actually, hGetContentsWithCursor seems like a candidate for inclusion with Data.ByteStrings or Data.Binary or something -- it seems like it might find other uses. (i think you liked that bit of code because i ripped it off of you guys! it's very short hamming distance from the original.) anyhow, all that will have to wait a couple weeks or so. also i've never cabalized anything so i may come begging for help. at some point i thought i saw how to do recursive external sort, to keep memory usage truly constant, but with my current lack of sleep i have lost that illusion. i'm also curious about the performance characteristics of this vs Prelude sort vs the version using the tournament mergesort apfelmus suggested. i need to find a computer with a lot more RAM than my weakling laptop. finally, it would be good to be able to have the blocksize controlled by Kb of RAM rather than # of elements, not sure how to get that information. ultimately this was part of my project to write lucene for haskell. i think with this out of the way, plus all the Data.Binary / ByteString goodness, it shouldn't take too long. keep writing good libraries for me! thanks and take care, Ben On 7/17/07, Donald Bruce Stewart [EMAIL PROTECTED] wrote: midfield: hi folks -- a haskell newbie here, searching for comments and wisdom on my code. i had a project to try to implement external sort in haskell as a learning exercise. (external sort is sorting a list that is too large to fit in main memory, by sorting in chunks, spooling to disk, and then merging. more properly there probably should be multiple stages, but for simplicity i'm doing a one-stage external sort.) the trick is the number of files can quickly grow very large, so it is best to use one large file and seek inside it around. however as one can imagine the order-of-IO-operations becomes a bit tricky, if you're seeking file handles around underneath Data.ByteString.Lazy's nose. but late this night after not thinking about it for a while i had a brainstorm: rewrite hGetContents to keep the handle position in the right place! it's all about judicious use of unsafeInterleaveIO. it seems to be rather fast, strangely faster than the usual sort at times. it also seems to have nice memory characteristics, though not perfect. it's hard to test because the normal sort function takes too much RAM on large lists, making my computer swap like mad. I have to agree with Mr. Apfelmus here. This is lovely code. It is exactly what the ByteString team hoped people would be able to write ByteStrings: Zen of Haskell code, where you win by working at a high level, rather than a low level. Thanks! I've inserted some small comments though the source: module ExternalSort where Sort a list of Ords offline. We're doing this to be able to sort things without taking up too much memory (for example sorting lists too large to fit in RAM.) Laziness is imperative, as is the order-of-operations. import Control.Monad import Data.List import qualified Data.Binary as Bin import qualified Data.ByteString.Lazy as B import qualified Data.ByteString as P (hGetNonBlocking, null) import Data.ByteString.Base (LazyByteString(LPS)) import Foreign.Storable (sizeOf) import System.IO (openFile, hClose, hSeek, hTell, hIsEOF, hWaitForInput, Handle, IOMode(ReadMode, WriteMode), SeekMode(AbsoluteSeek)) import System.IO.Unsafe (unsafeInterleaveIO) import qualified Data.Edison.Seq.ListSeq as LS import qualified Data.Edison.Coll.SplayHeap as Splay Conceptually, we sort a list in blocks, spool blocks to disk, then merge back. However for IO performance it is better to read off chunks of elements off the sorted blocks from disk instead of elements-at-a-time. It would be better if these were in KBytes instead of # of elements. blocksize :: Int blocksize = 1 Turn a list into a list of chunks. slice :: Int - [a] - [[a]] slice _ [] = [] slice size l = (take size l) : (slice size $ drop size l) That's unnecessary parenthesis, and I'd probably use splitAt here: myslice :: Int - [a] - [[a]] myslice _ [] = [] myslice n xs = a : myslice n b where (a,b) = splitAt n xs And just to check: *M :m + Test.QuickCheck *M Test.QuickCheck quickCheck (\n (xs :: [Int]) - n 0 == slice n xs == myslice n xs) OK, passed 100 tests. Turn a list into a list of blocks, each of which is sorted. blockify :: (Ord a) = Int - [a] - [[a]] blockify bsize l = map sort $ slice bsize l Possibly you could drop the 'l' parameter: blockify n = map sort . slice n Serialize a block, returning the (absolute)
Re: [Haskell-cafe] External Sort and unsafeInterleaveIO
midfield: hi -- thanks for the useful comments! i will definitely go through them carefully. unfortunately for this code (but fortunately for me) i defend my dissertation on monday so i'm a little distracted right now. i'm more than happy to donate this code or whatever improvements happen to it. actually, hGetContentsWithCursor seems like a candidate for inclusion with Data.ByteStrings or Data.Binary or something -- it seems like it might find other uses. (i think you liked that bit of code because i ripped it off of you guys! it's very short hamming Can't fault that style ;) distance from the original.) anyhow, all that will have to wait a couple weeks or so. also i've never cabalized anything so i may come begging for help. We have a tutorial for that, luckily: http://haskell.org/haskellwiki/How_to_write_a_Haskell_program And a tool to automate it, mkcabal, so should be fairly straightforward. at some point i thought i saw how to do recursive external sort, to keep memory usage truly constant, but with my current lack of sleep i have lost that illusion. i'm also curious about the performance characteristics of this vs Prelude sort vs the version using the tournament mergesort apfelmus suggested. i need to find a computer with a lot more RAM than my weakling laptop. finally, it would be good to be able to have the blocksize controlled by Kb of RAM rather than # of elements, not sure how to get that information. ultimately this was part of my project to write lucene for haskell. i think with this out of the way, plus all the Data.Binary / ByteString goodness, it shouldn't take too long. keep writing good libraries for me! Great. Good to see things working. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
