[Haskell-cafe] Split and substitution using regex-pcre
I could not find the perl-equivalents of these functions on Hackage, so I quickly wrote mine. Code is there: https://github.com/bartavelle/pcre-utils It should behave like perl (not really tested actually), and do strange things like : splitCompile a b Right [b] splitCompile a baaa Right [b] This will go on Hackage as I need it for the language-puppet package, but I am interested in comments, especially concerning the namespaces: * is the name of this package OK ? * is the name of the package OK ? * should I work with the regex-pcre maintainer to try to merge it ? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
On Wednesday, 20. February 2013 09:59:47 Tillmann Rendel wrote: So the grammar is: Exp ::= Int | Exp + Exp My naive parser enters an infinite recursion, when I try to parse 1+2. I do understand why: hmm, this expression could be a plus, but then it must start with an expression, lets check. and it tries to parse expression again and again considers Plus. Indeed. Twan van Laarhoven told me that: Left-recursion is always a problem for recursive-descend parsers. Note that the left recursion is already visible in the grammar above, no need to convert to parser combinators. The problem is that the nonterminal Exp occurs at the left of a rule for itself. Just a silly quick question: why isn't right-recursion a similar problem? -- Martin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
Hi Martin, Martin Drautzburg wrote: Note that the left recursion is already visible in the grammar above, no need to convert to parser combinators. The problem is that the nonterminal Exp occurs at the left of a rule for itself. Just a silly quick question: why isn't right-recursion a similar problem? I think the situation is symmetric: If you match the token stream right-to-left, right-recursion is problematic. Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Munich Haskell Meeting
Dear all, please note that our monthly Haskell get-together is scheduled on Wed, 27th Feb 2013 at 19h30 at Cafe Puck in Munich, Germany. If you plan to join, please go to http://www.haskell-munich.de/dates and click the button. Everyone interested in functional programming is welcome! I wish everyone of you, joining or not, a nice week, Heinrich ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
* Martin Drautzburg martin.drautzb...@web.de [2013-02-24 12:31:37+0100] Twan van Laarhoven told me that: Left-recursion is always a problem for recursive-descend parsers. Note that the left recursion is already visible in the grammar above, no need to convert to parser combinators. The problem is that the nonterminal Exp occurs at the left of a rule for itself. Just a silly quick question: why isn't right-recursion a similar problem? Right recursion is recursion of the form A ::= B A There are two cases to consider here. The language defined by B may or may not contain the empty string. If it contains the empty string, then we have an indirect left recursion, since the rule A ::= A is an instance of the original rule. If it doesn't contain the empty string, then, by the time you get to A, you necessarily have to consume some part of the input. Thus, your recursion is well-founded — you enter the recursion with the input strictly smaller than you had in the beginning. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
On Sun, Feb 24, 2013 at 7:09 PM, Roman Cheplyaka r...@ro-che.info wrote: Thus, your recursion is well-founded — you enter the recursion with the input strictly smaller than you had in the beginning. Perhaps you meant /productive/ corecursion? Because the definition A ::= B A you gave is codata. -- Kim-Ee ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
* Kim-Ee Yeoh k...@atamo.com [2013-02-24 19:22:33+0700] On Sun, Feb 24, 2013 at 7:09 PM, Roman Cheplyaka r...@ro-che.info wrote: Thus, your recursion is well-founded — you enter the recursion with the input strictly smaller than you had in the beginning. Perhaps you meant /productive/ corecursion? Because the definition A ::= B A you gave is codata. It is just a grammar production, which I chose to interpret recursively. Whether it's productive when interpreted corecursively depends on the particular interpretation, I guess, and may not actually depend on factors like left recursion. I haven't thought about it much. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
* Kim-Ee Yeoh k...@atamo.com [2013-02-24 19:22:33+0700] On Sun, Feb 24, 2013 at 7:09 PM, Roman Cheplyaka r...@ro-che.info wrote: Thus, your recursion is well-founded — you enter the recursion with the input strictly smaller than you had in the beginning. Perhaps you meant /productive/ corecursion? Because the definition A ::= B A you gave is codata. Or perhaps you meant that the production itself, when interpreted as a definition, is corecursive? Well, yes, and so is any CFG written in BNF. But that doesn't buy us much, and is irrelevant to the discussion of parsing left-recursive grammars. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
On Sun, Feb 24, 2013 at 7:47 PM, Roman Cheplyaka r...@ro-che.info wrote: Or perhaps you meant that the production itself, when interpreted as a definition, is corecursive? I was merely thrown off by your mention of well-founded and the assertion that you're left with a strictly smaller input. I don't see any of this. That's when I remembered that well-founded recursion (a desirable) is sometimes confused with productive corecursion (another desirable). -- Kim-Ee ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
* Kim-Ee Yeoh k...@atamo.com [2013-02-24 19:56:13+0700] I was merely thrown off by your mention of well-founded and the assertion that you're left with a strictly smaller input. I don't see any of this. It may become more obvious if you try to write two recursive descent parsers (as recursive functions) which parse a left-recursive and a non-left-recursive grammars, and see in which case the recursion is well-founded and why. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
On Sun, Feb 24, 2013 at 8:03 PM, Roman Cheplyaka r...@ro-che.info wrote: It may become more obvious if you try to write two recursive descent parsers (as recursive functions) which parse a left-recursive and a non-left-recursive grammars, and see in which case the recursion is well-founded and why. Which grammar are we discussing here? The one you outlined? A ::= B A As I pointed out earlier, this doesn't model a program (e.g. a compiler). It's an OS! What am I missing? -- Kim-Ee ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install ghc-mod installs 3 years old version
You are right, my ghc-7.4.2 was broken in ghc-pkg list; I fixed the problem by killing my .cabal folder (as so often). Do you know if it is possible to make ghc-pkg list print some actual text when packages are broken instead of writing them in red (which goes away on output redirection)? Thanks Niklas On 24/02/13 07:34, Ivan Lazar Miljenovic wrote: Which version of GHC (and hence base, etc.)? My guess is that for some reason it thinks that some requirement of the later versions is incompatible with your version of GHC. Maybe explicitly try cabal install 'ghc-mod = 1.11.4' and see why it doesn't like it. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
On Sun, Feb 24, 2013 at 6:31 AM, Martin Drautzburg martin.drautzb...@web.de wrote: Just a silly quick question: why isn't right-recursion a similar problem? Very roughly: Left recursion is: let foo n = n + foo n in ... Right recursion is: let foo 1 = 1; foo n = n + foo (n - 1) in ... In short, matching the tokens before the right recursion will constitute an end condition that will stop infinite recursion --- if only because you'll hit the end of the input. Left recursion doesn't consume anything, just re-executes itself. -- brandon s allbery kf8nh sine nomine associates allber...@gmail.com ballb...@sinenomine.net unix, openafs, kerberos, infrastructure, xmonadhttp://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
Hi, Kim-Ee Yeoh wrote: Perhaps you meant /productive/ corecursion? Because the definition A ::= B A you gave is codata. If you write a recursive descent parser, it takes the token stream as an input and consumes some of this input. For example, the parser could return an integer that says how many tokens it consumed: parseA :: String - Maybe Int parseB :: String - Maybe Int Now, if we implement parseA according to the grammar rule A ::= B A we have, for example, the following: parseA text = case parseB text of Nothing - Nothing Just n1 - case parseA (drop n1 text) of Nothing - Nothing Just n2 - Just (n1 + n2) Note that parseA is recursive. The recursion is well-founded if (drop n1 text) is smaller then text. So we have two cases, as Roman wrote: If the language defined by B contains the empty string, then n1 can be 0, so the recursion is not well-founded and the parser might loop. If the language defined by B does not contain the empty string, then n1 is always bigger than 0, so (drop n1 text) is always smaller than text, so the recursion is well-founded and the parser cannot loop. So I believe the key to understanding Roman's remark about well-founded recursion is to consider the token stream as an additional argument to the parser. However, the difference between hidden left recursion and unproblematic recursion in grammars can also be understood in terms of productive corecursion. In that view, a parser is a process that can request input tokens from the token stream: data Parser = Input (Char - Parser) | Success | Failure parseA :: Parser parseB :: Parser Now, if we implement parseA according to the grammar rule A ::= B A we have, for example, the following: andThen :: Parser - Parser - Parser andThen (Input f) p = Input (\c - f c `andThen` p) andThen (Success) p = p andThen Failure p = p parseA = parseB `andThen` parseA Note that parseA is corecursive. The corecursion is productive if the corecursive call to parseA is guarded with an Input constructor. Again, there are two cases: If the language described by B contains the empty word, then parseB = Success, and (parseB `andThen` parseA) = parseA, so the corecursive call to parseA is not guarded and the parser is not productive. If the langauge described by B does not contain the empty word, then parseB = Input ..., and (parseB `andThen` parseA) = Input (... parseA ...), so the corecursive call to parseA is guarded and the parse is productive. So I believe the key to understanding left recursion via productive corecursion is to model the consumption of the token stream with a codata constructor. Both approaches are essentially equivalent, of course: Before considering the very same nonterminal again, we should have consumed at least one token. Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Install qtHaskell 1.1.4 using Visual Studio 2010 and GHC 7.4.2
I am trying to install qtHaskell in Windows. I have Qt 4.8.4 (the Visual Studio 2010 version). I am following the section 2.3.2 Windows Manual Installation from the userGuide of qtHaskell. I set the path as described I added the line to qt.cabal, I changed dir to qws I gave qmake -recursive and then instead of mingw32-make I gave nmake which is the equivalent for VS2010. After the compilation process finished with success I switched back to root directory of qtHaskell and I gave runhaskell Setup.hs configure --ghc and I took the message: Setup.hs:1:12: Warning: -fglasgow-exts is deprecated: Use individual extensions instead Configuring qt-1.1.4... After that I gave the command: runhaskell Setup.hs makefile and I got the message: Setup.hs:1:12: Warning: -fglasgow-exts is deprecated: Use individual extensions instead unrecognised command: makefile (try --help) Any help in order to continue? Thank in advance ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Thunks and GHC pessimisation
To avoid retaining a large lazy data structure in memory it is useful to
hide it behind a function call. Below, many is used twice. It is hidden
behind a function call so it can be garbage collected between uses. That's
good. When compiling with -O it seems that GHC 7.4.1 decides to keep it
in memory anyway. That's bad. (I can't read core so I don't know exactly
what's going on). Replacing one of the many in twice with
different_many makes everything fine again.
Is this considered a bug in GHC? Is it a known bug? It is incredibly
concerning that GHC would perform this kind of pessimisation.
Tom
% cat thunkfail.hs
{-# OPTIONS_GHC -fno-warn-unused-binds #-}
import Data.List
million :: Int
million = 10 ^ (6 :: Int)
many :: () - [Int]
many () = [1..million]
different_many :: () - [Int]
different_many () = [1..million]
twice :: (Int, Int)
twice = (foldl' (+) 0 (many ()), foldl' (+) 0 (many ()))
main :: IO ()
main = print twice
% ghc -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs ./thunkfail +RTS
-M5M
[1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o )
Linking thunkfail ...
(1784293664,1784293664)
% ghc -O -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs ./thunkfail +RTS
-M5M
[1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o )
Linking thunkfail ...
Heap exhausted;
Current maximum heap size is 5242880 bytes (5 MB);
use `+RTS -Msize' to increase it.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Thunks and GHC pessimisation
Hi, I believe, without checking, that Am Sonntag, den 24.02.2013, 17:49 + schrieb Tom Ellis: many :: () - [Int] many () = [1..million] is indeed called many times. The problem is that [1..million] is not dependent on the parameter, so GHC will float it out to a top level declaration, and hence share it between the multiple calls to many. You should try: million :: () - Int million _ = 10 ^ (6 :: Int) many :: () - [Int] many x = [1..million x] Greetings, Joachim (Maybe I should continue to work on http://arxiv.org/abs/1106.3478 and related ideas, like annotating thunks in the code as unshareable... or does this mostly occur in small example programs like this?) -- Joachim nomeata Breitner Debian Developer nome...@debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nome...@joachim-breitner.de | http://people.debian.org/~nomeata signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Thunks and GHC pessimisation
In toy examples like this it will be generally hard to convince GHC not to
just collapse your program down to a constant, when you're turning up the
optimization level.
In particular, you are implying -ffull-laziness with -O (or -O2), which can
increase sharing.
GHC doesn't implement complete full-laziness. When optimisation in on,
and -fno-full-laziness is not given, *some transformations that increase
sharing are performed, such as extracting repeated computations from a loop*.
These are the same transformations that a fully lazy implementation would
do, the difference is that GHC doesn't consistently apply full-laziness, so
don't rely on it.
http://www.haskell.org/ghc/docs/latest/html/users_guide/options-optimise.html
If you explicitly rely on this not happening, turn it off:
$ ghc -O2 -fno-full-laziness --make A.hs -rtsopts -fforce-recomp
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
$ time ./A +RTS -M750k
(5050,5050)
./A +RTS -M750k 0.06s user 0.00s system 97% cpu 0.069 total
A 750k heap should be enough for anyone :)
-- Don
On Sun, Feb 24, 2013 at 5:49 PM, Tom Ellis
tom-lists-haskell-cafe-2...@jaguarpaw.co.uk wrote:
To avoid retaining a large lazy data structure in memory it is useful to
hide it behind a function call. Below, many is used twice. It is hidden
behind a function call so it can be garbage collected between uses. That's
good. When compiling with -O it seems that GHC 7.4.1 decides to keep it
in memory anyway. That's bad. (I can't read core so I don't know exactly
what's going on). Replacing one of the many in twice with
different_many makes everything fine again.
Is this considered a bug in GHC? Is it a known bug? It is incredibly
concerning that GHC would perform this kind of pessimisation.
Tom
% cat thunkfail.hs
{-# OPTIONS_GHC -fno-warn-unused-binds #-}
import Data.List
million :: Int
million = 10 ^ (6 :: Int)
many :: () - [Int]
many () = [1..million]
different_many :: () - [Int]
different_many () = [1..million]
twice :: (Int, Int)
twice = (foldl' (+) 0 (many ()), foldl' (+) 0 (many ()))
main :: IO ()
main = print twice
% ghc -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs ./thunkfail
+RTS -M5M
[1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o )
Linking thunkfail ...
(1784293664,1784293664)
% ghc -O -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs ./thunkfail
+RTS -M5M
[1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o )
Linking thunkfail ...
Heap exhausted;
Current maximum heap size is 5242880 bytes (5 MB);
use `+RTS -Msize' to increase it.
___
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] Thunks and GHC pessimisation
On Sun, Feb 24, 2013 at 07:12:24PM +0100, Joachim Breitner wrote:
You should try:
million :: () - Int
million _ = 10 ^ (6 :: Int)
many :: () - [Int]
many x = [1..million x]
Thanks Joachim, but that doesn't work either.
Tom
% cat thunkfail.hs
{-# OPTIONS_GHC -fno-warn-unused-binds #-}
import Data.List
million :: () - Int
million _ = 10 ^ (6 :: Int)
many :: () - [Int]
many x = [1..million x]
different_many :: () - [Int]
different_many x = [1..million x]
twice :: (Int, Int)
twice = (foldl' (+) 0 (many ()), foldl' (+) 0 (many ()))
main :: IO ()
main = print twice
% ghc -O -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs ./thunkfail
% +RTS -M5M
[1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o )
Linking thunkfail ...
Heap exhausted;
Current maximum heap size is 5242880 bytes (5 MB);
use `+RTS -Msize' to increase it.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Thunks and GHC pessimisation
On Sun, Feb 24, 2013 at 06:25:56PM +, Don Stewart wrote: If you explicitly rely on this not happening, turn it off: $ ghc -O2 -fno-full-laziness --make A.hs -rtsopts -fforce-recomp [1 of 1] Compiling Main ( A.hs, A.o ) Linking A ... $ time ./A +RTS -M750k (5050,5050) ./A +RTS -M750k 0.06s user 0.00s system 97% cpu 0.069 total Thanks Don, that's good to know. I am not currently bitten by this issue in any production code, but I am concerned it will crop up when I least expect it. Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
On Sun, Feb 24, 2013 at 10:04 PM, Tillmann Rendel ren...@informatik.uni-marburg.de wrote: The recursion is well-founded if (drop n1 text) is smaller then text. So we have two cases, as Roman wrote: If the language defined by B contains the empty string, then n1 can be 0, so the recursion is not well-founded and the parser might loop. Ah! So A ::= B A is really /not/ the full grammar of the language but an abbreviated one, minus terminals. At the very least, partial parses make sense and the input stream is assumed finite. Because A ::= B A could be understood, not so much as a parsing rule, but as the full definition of a language which comprises only one word: B ... ad infinitum. So all that mention of well-foundedness was confusing. Thanks, Tillmann! -- Kim-Ee ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] presentation on Diffusion of Innovation mentioning several times Haskell
Just found an Interesting presentation mixing Diffusion of Innovation with Social Patterns, mentioning several times Haskell. Good introduction to a mix of techniques for whoever interested in Haskell proselytism, and go to market strategy, http://www.taesch.com/haskell/go-to-market/introduction-to-diffusion-of-innovation-and-sociology-and-haskell-go-to-market-strategy/2013/02/24/276 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install ghc-mod installs 3 years old version
On 25 February 2013 01:33, Niklas Hambüchen m...@nh2.me wrote: You are right, my ghc-7.4.2 was broken in ghc-pkg list; I fixed the problem by killing my .cabal folder (as so often). Do you know if it is possible to make ghc-pkg list print some actual text when packages are broken instead of writing them in red (which goes away on output redirection)? Just run ghc-pkg check every now and then? Thanks Niklas On 24/02/13 07:34, Ivan Lazar Miljenovic wrote: Which version of GHC (and hence base, etc.)? My guess is that for some reason it thinks that some requirement of the later versions is incompatible with your version of GHC. Maybe explicitly try cabal install 'ghc-mod = 1.11.4' and see why it doesn't like it. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parser left recursion
On 2/24/13 7:56 AM, Kim-Ee Yeoh wrote: On Sun, Feb 24, 2013 at 7:47 PM, Roman Cheplyaka r...@ro-che.info wrote: Or perhaps you meant that the production itself, when interpreted as a definition, is corecursive? I was merely thrown off by your mention of well-founded and the assertion that you're left with a strictly smaller input. I don't see any of this. But the problem here really is an issue of well-foundedness rather than productivity. Consider the grammar, A ::= epsilon | A B B ::= ...whatever... In order to use this grammar as-is, when processing a string we must be able to magically determine how many times to recurse in order to get our epsilon. This is magic because the correct number of times to recurse is defined by the rest of the string--- which we haven't looked at! Proof theoretically speaking, this is the same as magically knowing when to use the inductive hypothesis vs when to bottom out at a base case. Using this grammar as-is, the recursive descent parser always decides to use the inductive hypothesis. Hence, infinite loop. It should be apparent that this isn't an issue with left-recursion (when reading the string from right to left), because on left-recursion we're always consuming some of the string, and therefore the input string is getting smaller on each recursive call, and therefore it is guaranteed that we will eventually run out of string, at which point we can backtrack as necessary. The problem with right-recursion is that we never know when to stop recurring. If we stop at some arbitrary point, well maybe the parse will end up failing when it could've succeeded if only we had recursed a bit further. But recursive descent doesn't allow the kind of backtracking that would be required to exhaust the search space for right-recursion. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Tournament knock out
Hi, Tournament knock out is explained in [1] by Knuth. The limitation is that it can only handle the sequence of the length 2^m for some integer m. When the champion element is removed, it was replaced with negative infinity. Typically negative infinity is represented by a predefined big negative number. Although heap sort solves all these limitation, I found tournament knock out itself can work out. Here is the Haskell code: data Infinite a = NegInf | Only a | Inf deriving (Eq, Show, Ord) only (Only x) = x data Tr a = Empty | Br (Tr a) a (Tr a) deriving Show key (Br _ k _ ) = k wrap x = Br Empty (Only x) Empty branch t1 t2 = Br t1 (min (key t1) (key t2)) t2 fromList :: (Ord a) = [a] - Tr (Infinite a) fromList = build . (map wrap) where build [] = Empty build [t] = t build ts = build $ pair ts pair (t1:t2:ts) = (branch t1 t2):pair ts pair ts = ts pop (Br Empty _ Empty) = Br Empty Inf Empty pop (Br l k r) | k == key l = let l' = pop l in Br l' (min (key l') (key r)) r | k == key r = let r' = pop r in Br l (min (key l) (key r')) r' top = only . key tsort :: (Ord a) = [a] - [a] tsort = sort' . fromList where sort' Empty = [] sort' (Br _ Inf _) = [] sort' t = (top t) : (sort' $ pop t) The detailed explanation can be found at: https://github.com/liuxinyu95/AlgoXY/blob/algoxy/preview/ssort-en.pdf?raw=true [1]. Donald E. Knuth. The art of computer programming, Volume 3, sorting and searching. Larry, LIU Xinyu https://sites.google.com/site/algoxy/ https://github.com/liuxinyu95/AlgoXY ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ifdef based on which OS you're on
On Sun, Feb 24, 2013 at 5:28 PM, Andrew Cowie and...@operationaldynamics.com wrote: On Sat, 2013-02-16 at 08:18 +0100, Henk-Jan van Tuyl wrote: Anyone have any idea if the Cabal library exposes this somewhere? See... I blogged about my solution using Krzysztof and Henk's suggestions here: http://blogs.operationaldynamics.com/andrew/software/haskell/config-dot-h-and-ifdef Cheers everyone, I read your blog post and I'm afraid I don't see the point: you write some code to tap into a pre-existing library that figures out what platform you are on so that you can write out a 'config.h' that #define's the platform you are on so that you can then use the C preprocessor to pick a particular code path via conditional compilation. Why go to all that bother? Why not just write code that writes out the path you want to take and link against it? - Dan C. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: conduit-network-stream, A base layer for network protocols with Conduits
Hello, Nils.
Can you describe if there any difference with latest conduit API (yield,
await) that can be
used to write functions in a very similar style, but without using
exeternal packages:
runTCPServer settings app = appSource ap $$ go =$= CL.mapM_ encode =$
appSink app
where
go = forever $ do
bp - decode $ await {- decode is inlined here assuming it
can return different types -}
{- logic here-}
yield $ result
mapM (yeild) [result1,result2...]
more over you don't need to write appSource $$ ... appSink on the top.
Here is an example of a client that authorizes and then reads commands
from TBMChan and requests server using json format.
runTCPClient settings ad go
where
go = do
source $$ await
is - authorize
when is loop'
authorize = do
yield u yield (S8.pack \n) $$ sink -- send authorization
token
mx - source $$ sinkParser json -- get responce
...
loop' = do
minfo - atomically $ readTBMChan ch
case minfo of
Nothing - return ()
Just (message, respBox) - do
yield message $$ C.concatMap (SL.toChunks . encode) =$ sink
resp - source $$ sinkParser json
atomically $ putTMVar respBox resp
loop'
source = ppSource ad
sink = appSink ad
On 24 February 2013 22:23, Nils m...@nils.cc wrote:
Hello everyone,
I just uploaded my conduit-network-stream package to hackage. It's a
base layer for network protocols based on the Conduit package by Michael
Snoyman which makes it possible to send multiple messages over a continuous
network connection in a convenient way.
I wrote more about it at:
https://github.com/mcmaniac/**conduit-network-stream/blob/**
master/README.mdhttps://github.com/mcmaniac/conduit-network-stream/blob/master/README.md
It is available on hackage and github:
http://hackage.haskell.org/**package/conduit-network-streamhttp://hackage.haskell.org/package/conduit-network-stream
https://github.com/mcmaniac/**conduit-network-streamhttps://github.com/mcmaniac/conduit-network-stream
Until the documentation on hackage is generated, I also host the haddock
documentation at:
http://hs.nils.cc/conduit-**network-stream/index.htmlhttp://hs.nils.cc/conduit-network-stream/index.html
For any questions/problems/requests, please ask!
- Nils
__**_
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe
--
Alexander
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] RFC: rewrite-with-location proposal
Quite a while back, Simon Hengel and I put together a proposal[1] for a new
feature in GHC. The basic idea is pretty simple: provide a new pragma that
could be used like so:
error :: String - a
errorLoc :: IO Location - String - a
{-# REWRITE_WITH_LOCATION error errorLoc #-}
Then all usages of `error` would be converted into calls to `errorLoc` by
the compiler, passing in the location information of where the call
originated from. Our three intended use cases are:
* Locations for failing test cases in a test framework
* Locations for log messages
* assert/error/undefined
Note that the current behavior of the assert function[2] already includes
this kind of approach, but it is a special case hard-coded into the
compiler. This proposal essentially generalizes that behavior and makes it
available for all functions, whether included with GHC or user-defined.
The proposal spells out some details of this approach, and contrasts with
other methods being used today for the same purpose, such as TH and CPP.
Michael
[1] https://github.com/sol/rewrite-with-location
[2]
http://hackage.haskell.org/packages/archive/base/4.6.0.1/doc/html/Control-Exception.html#v:assert
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
