- Haskell-Cafe - Haskell.org

Very fast searching of byte strings
by ChrisK 17 Aug '07

17 Aug '07

Post the the library mailing list at [1] is the Boyer-Moore algorithm implemented for strict and lazy bytestrings (and combinations thereof). It finds all the overlapping instances of the pattern inside the target. I have performance tuned it. But the performance for searching a strict bytestring is better then for a lazy bytestring (even if they only had a single strict chunk), which almost certainly means I was not clever enough to get GHC to produce the optimal code. There is much more description in the module's haddock header. Hopefully Don or other ByteString experts/maintainers can tweak this even further. Also at [1] is a Knuth-Morris-Pratt module which find non-overlapping instances and is slightly slower on my benchmarks. Happy Searching, Chris Kuklewicz [1] http://www.haskell.org/pipermail/libraries/2007-August/007987.html

1 0

Re: [Haskell-cafe] Basic question....
by Janis Voigtlaender 17 Aug '07

17 Aug '07

----- Ursprüngliche Nachricht ----- Von: "rodrigo.bonifacio" <rodrigo.bonifacio(a)uol.com.br> Datum: Freitag, August 17, 2007 3:11 pm Betreff: [Haskell-cafe] Basic question.... > Hi all. > > I want to create the following polymorphic type (EnvItem) that we > can apply two functions (envKey and envValue). I tried the following: > > > type Key = String > > > data EnvItem a = EnvItem (Key, a) > > > envKey :: EnvItem (Key, a) -> String > > envKey EnvItem (key, value) = key > > > envValue :: EnvValue(Key, a) -> a > > envValue EnvItem (key, value) = value > > But this is resulting in the error: [Constructor "EnvItem" must > have exactly 1 argument in pattern] > > I think this is a very basic problem, but I don't know what is wrong. You are simply missing some brackets: > envKey :: EnvItem (Key, a) -> String > envKey (EnvItem (key, value)) = key > envValue :: EnvValue(Key, a) -> a > envValue (EnvItem (key, value)) = value Ciao, Janis.

3 3

So far, so good! Until... (Haskell 98 Report questions)
by Ian Duncan 17 Aug '07

17 Aug '07

... I hit Chapter 3 and started reading about expressions. *If you are able to answer any of these questions, please send me an email. I am very lost and confused in this section, so even one answered question may help greatly.* I actually decided to sit down and figure out the Haskell 98 Report today. Everything was going well until I began Chapter 3. Here's the section that has me baffled: "In the syntax that follows, there are some families of nonterminals indexed by precedence levels (written as superscript). Similarly, the nonterminals op, varop, and conop may have a double index: a letter l, r, or n for left-, right- or non-associativity and a precedence level. A precedence-level variable i ranges from 0 to 9; an associativity variable, a, varies over {l,r,n}. For example, aexp -> ( exp^(i+1) qop^(a,i) ) actually stands for 30 productions, with 10 substitutions for i and 3 for a." *note that the "^" was used to indicate superscript. So here's my list of questions so far: 1. What are nonterminals? 2. What are productions and substitutions? I tried the dictionary and wikipedia, but neither were very helpful in defining those terms. Next, it says: exp -> exp^0 :: [context=>] type (expression type signature) | exp^0 exp^i -> exp^(i+1) [qop^(n,i) exp^(i+1)] | lexp^i | rexp^i ... From there it continues with more syntax stuff, but I'll stop there for the sake of not typing too much. So here are some questions about this section: 1. What the heck is going on? 2. How is an expression with a precedence of i considered to be an expression of i+1? 3. Within the ... section it mentions lexp and rexp. Do those stand for left-associative expressions and right-associative expressions respectively? I understand the concept of fixity when I see it mentioned in code, but I truly have no idea what 3.0 is talking about. Can anyone shed some light on any of this? I'm still in high school, so if anyone could please explain it to me in layman's terms primarily, or provide some resources explaining more complex terms, It would be greatly appreciated. Thanks a bunch! Ian Duncan

3 2

Hints for Euler Problem 11
by Ronald Guida 17 Aug '07

17 Aug '07

Hi, again. I started looking at the Euler problems [1]. I had no trouble with problems 1 through 10, but I'm stuck on problem 11. I am aware that the solutions are available ([2]), but I would rather not look just yet. In Problem 11, a 20x20 grid of numbers is given, and the problem is to find the largest product of four numbers along a straight line in the grid. The line can be horizontal, vertical, or diagonal. I figured out how to handle the horizontal and vertical products, but I'm stuck on how to approach the problem of extracting the diagonals. Here is what I have so far; it does the horizontal and vertical cases: > module Main > where > > import Data.List > > gridText = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n\ > \49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n\ > \81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n\ > \52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n\ > \22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n\ > \24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n\ > \32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n\ > \67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n\ > \24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n\ > \21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n\ > \78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n\ > \16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n\ > \86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n\ > \19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n\ > \04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n\ > \88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n\ > \04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n\ > \20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n\ > \20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n\ > \01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48" > > readGrid :: (Read a) => String -> [[a]] > readGrid = (map ((map read) . words)) . lines > > grid :: [[Integer]] > grid = readGrid gridText > > makeGroups :: Int -> [a] -> [[a]] > makeGroups 0 _ = [] > makeGroups n xs = let ys = take n xs in > if n == length ys > then ys : (makeGroups n $ tail xs) > else [] > > maxHorizontal :: (Ord a, Num a) => Int -> [[a]] -> a > maxHorizontal length = maximum . map product . concat . map (makeGroups length) > > maxVertical :: (Ord a, Num a) => Int -> [[a]] -> a > maxVertical length = maxHorizontal length . transpose > > main :: IO() > main = do > print $ maxHorizontal 4 grid > print $ maxVertical 4 grid To handle the diagonals, my plan is to try to extract each diagonal as a list of elements and put all the diagonals into a list; then I can use maxHorizontal. I came up with this function to try to extract the main diagonal. > getDiag :: [[a]] -> [a] > getDiag = map (head . head) . iterate (tail . map tail) The problem is, this function doesn't work unless I have an infinite grid. Could anyone provide me with some hints to lead me in the right direction? Thank you -- Ron References: [1] http://projecteuler.net/index.php?section=view [2] http://www.haskell.org/haskellwiki/Euler_problems

7 7

Collada, FBX, XML schemas and Haskell?
by Peter Verswyvelen 17 Aug '07

17 Aug '07

I wanted to do some experiments with HOpenGL, and one of the things I tried is importing 3D models. So I searched for a library that could do that, but besides Frag, who uses the limited MD3 format, I did not find anything useful. Has any work been done on supporting that? Maybe just converting the 3D format into a series of HOpenGL calls (tools like that exists for C)? It would be nice to support Collada, one of the two standards for 3D models in the game industry. It is fully open and has exporters for most major 3D modeling packages. See http://en.wikipedia.org/wiki/COLLADA. The other standard is FBX, but that's a proprietary format from Autodesk. Collada comes with a full XML schema. Is it possible to convert an XML schema into Haskell data/code that automatically handles reading documents that follow the schema, as is commonly done when using Java or .NET? I looked at some XML libraries for Haskell, but could not figure out if they supported something like that. I can find the tools I need for C# or Java in an instance, but when it comes to Haskell I have difficulties understanding even the basic descriptions of some of the libraries ;-) Of course, that is because I'm a newbie in Haskell land and don't have a PhD degree, but it does make development in Haskell very frustrating! ;-) Thanks, Peter

2 1

trouble building 6.7 on ubuntu
by Thomas Hartman 17 Aug '07

17 Aug '07

I have gotten ghc 6.7 to compile, but not with extra libs. I'm on linux x86, ubuntu. Can someone suggest a download date that worked for them, or how to fix one or more of the problems described below? When I build from source (this is for august 2, unknown linux, as conal spoke well of it :) but I have tried with several other dates in august with the same result) I get Linux linuxpt 2.6.15-23-386 #1 PREEMPT Tue May 23 13:49:40 UTC 2006 i686 GNU/Linux The programs included with the Ubuntu system are free software; checking host system type... i686-pc-linux-gnu checking target system type... i686-pc-linux-gnu Which we'll further canonicalise into: i386-unknown-linux checking for path to top of build tree... ./configure: line 1433: cd: utils/pwd: No such file or directory ./configure: line 1438: -v0: command not found ./configure: line 1441: utils/pwd/pwd: No such file or directory configure: error: cannot determine current directory when I try unzip src and extralibs I get (aug 15... tail of a large out file after >1.5 hours of configure; make > out.txt) ...... make[1]: Leaving directory `/home/hartthoma/installs/ghc6.7/aug15/ghc-6.7.20070815/libraries' make -C libraries all make[1]: Entering directory `/home/hartthoma/installs/ghc6.7/aug15/ghc-6.7.20070815/libraries' rm -f -f stamp/configure.library.*.base base/unbuildable ( cd base && setup/Setup configure \ --enable-library-profiling --enable-split-objs \ --prefix='$topdir' \ --datadir='$prefix/share/ghc' \ --datasubdir='.' \ --libsubdir='$compiler/lib/$pkgid' \ --with-compiler=../../compiler/stage1/ghc-inplace\ --with-hc-pkg=../../utils/ghc-pkg/ghc-pkg-inplace\ --with-hsc2hs=../../utils/hsc2hs/hsc2hs-inplace \ --with-ld=/usr/bin/ld \ --haddock-args="--use-contents=../index.html \ --use-index=../doc-index.html" \ \ --configure-option=--with-cc=gcc ) \ && touch stamp/configure.library.build-profiling-splitting.base || touch base/unbuildable Setup: Warning: Unknown fields: nhc98-options (line 173) Fields allowed in this section: buildable, cc-options, ld-options, frameworks, c-sources, extensions, extra-libraries, extra-lib-dirs, includes, install-includes, include-dirs, hs-source-dirs, other-modules, ghc-prof-options, ghc-options, hugs-options, nhc-options, jhc-options, exposed-modules Setup: Warning: A package using section syntax should require "Cabal-Version: >= 1.2" or equivalent. HsColour 1.6 configure: Reading installed packages... Configuring base-2.1... configure: Flags chosen: isghc=True configure: Dependency rts-any: using rts-1.0 Setup: executing external program failed (exit 1) : /usr/local/bin/HsColour -version rm -f base/GNUmakefile cp Makefile.local base if ifBuildable/ifBuildable base; then \ cd base && setup/Setup makefile -f GNUmakefile; \ fi Setup: error reading dist/setup-config; run "setup configure" command? make[1]: *** [base/GNUmakefile] Error 1 make[1]: Leaving directory `/home/hartthoma/installs/ghc6.7/aug15/ghc-6.7.20070815/libraries' make: *** [stage1] Error 2 very weird error because when I execute /usr/local/bin/HsColour -version it doesn't fail but outputs 1.6. Can somebody suggest a download date known to compile (with extralibs) for ubuntu? Or suggest a fix? By the way I have also tried darcs get http://hackage.haskell.org/trac/ghc but this dies about halfway through (in the patch 10000s ) with libcurl error 18 or libcurl error 404 depending on the phase of the moon. I'm currently trying a build from darcs checkout with get --partial. If this is the preferred way of doing a checkout due to "crapping out halfway" issues maybe it should be said in the readme. (to be honest I forget what the difference between a partial darcs get and a complete get is.) Much obliged, thomas. "Conal Elliott" <conal(a)conal.net> Sent by: cvs-ghc-bounces(a)haskell.org 08/15/2007 06:38 PM To cvs-ghc(a)haskell.org cc Subject Fwd: how to get packages for HEAD snapshot ? oops -- meant to cc cvs-ghc btw, 20070802 does run and does have libs included. ---------- Forwarded message ---------- From: Conal Elliott < conal(a)conal.net> Date: Aug 15, 2007 2:56 PM Subject: Re: how to get packages for HEAD snapshot ? To: Stefan O'Rear <stefanor(a)cox.net> Thank Stefan, The latest mingw32 snapshot I see is 20070811. I installed it also, and when I run ghc, it just crashes (WinXP). Happens when I run it inside of emacs and also in a cygwin bash window. Is that a known problem? - Conal On 8/15/07, Stefan O'Rear < stefanor(a)cox.net> wrote: On Wed, Aug 15, 2007 at 02:20:53PM -0700, Conal Elliott wrote: > I installed ghc-6.7.20070810-i386-unknown-mingw32.exe. Though it runs, I > don't know how to get other packages installed, including Cabal. "ghc-pkg > list" tells me that I have only {ghc-6.7.20070810}, rts-1.0. > > Any suggestions? Upgrade GHC; Cabal should be installed but wasn't due to a bug in that snapshot. Stefan -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFGw3AnFBz7OZ2P+dIRArOwAKCMEEzbB/JwEYnA21wZb4gf1rCoDQCeL1DG u5ljAbmfp5j0sd5X51nf3wk= =hewc -----END PGP SIGNATURE----- _______________________________________________ Cvs-ghc mailing list Cvs-ghc(a)haskell.org http://www.haskell.org/mailman/listinfo/cvs-ghc --- 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.

2 1

Re: trouble building 6.7 on ubuntu
by Esa Ilari Vuokko 17 Aug '07

17 Aug '07

On 8/16/07, Thomas Hartman <thomas.hartman(a)db.com> wrote: > > > I repeated the install attempt described below using darcs head, including > the extra libs. > > I got the exact same error as before. > > Setup: Warning: Unknown fields: nhc98-options (line 173) .... and then a > cryptic error involving HsColour > > I think you run into Cabal bug - you need to remove (or upgrade?) HsColour in your path, if that's the case. Best regards, Esa

2 1

Syntax for lambda case proposal could be "\of"
by Brian Hulley 17 Aug '07

17 Aug '07

Hi, On http://hackage.haskell.org/trac/haskell-prime/wiki/LambdaCase the proposed syntax for lambda case is: case of alts but this has a really bad downside for interactive editors: it doesn't allow one to distinguish between an incomplete construct and a completed construct thus removing one opportunity for an editor to alert the user (eg by highlighting) that there is something missing in the program text. Therefore I propose: \of alts which doesn't suffer this problem since the keyword "of" can never follow a '\' in the existing grammar. However I can't edit the H' wiki, so if anyone agrees that the above syntax is better please could they add the above to the page. Thanks, Brian.

9 12

Pattern matching articles/explanations
by Ian Duncan 17 Aug '07

17 Aug '07

So what I noticed that "A Gentle Introduction to Haskell" mentioned that wild-cards are useful in constructors. For example: head (x:_) = x So, does that offer any performance benefits over: head (x:xs) = x Or is it primarily to indicate to the coder that xs is useless? I get the impression it has a very similar meaning to the irrefutable pattern in regards to not evaluating it when the function is called. Or am I way off?

3 2

Re: hyperlinked haskell 98 grammar
by Peter Hercek 17 Aug '07

17 Aug '07

Hi Neil, For haskell-cafe members: This is what we are talking about: http://www.hck.sk/users/peter/ I'm glad somebody liked it. I do not understand what you mean by the extension request. Would you want to see the number of references of a production head even without opening the popup list box? If you meant that the pop-up list box should always display all backward links directly (without a scroll bar) then it would not work for a very big number of such links (in theory there can be hundreds there). If you do not like the default of 5 then change the nMaxRowCount "constant". Anyway, if it is complicated to describe, let it be. I do not expect to play with the java script code much. Only the most trivial things have a chance to be implemented by me. I have written the java script code few years ago and I do not really like java script ... Just wanted to give back something to the community - so I added the Haskell specific data. As for as putting it on the Haskell org I do not mind if somebody else does it. Although I'm not that sure if it would require license change. If I would believe giving it into public domain would make more grammars browsable like this one then I would do it. I do not really expect heavy loads. From my experience most language users never ever look at the grammar nor they care about it. And those who consult it a lot will take a local copy and tweak it anyway. Looking at the munin server loads, looks like you and Esa are the only ones who actually checked it out :-D Anyway, sending this to haskell cafe too (as recommended). I expect a discussion (if any) will continue there. Sorry about GHC user list abuse. Peter Hercek. Neil Mitchell wrote: > Hi > > In addition, perhaps this should be relocated to haskell.org, if your > server is not suitable for a large volume of users. I think it should > also be integrated somewhere (perhaps a link from the HTML report, and > certainly on the wiki) > > Thanks > > Neil > > On 8/16/07, Neil Mitchell <ndmitchell(a)gmail.com> wrote: >> Hi Peter, >> >> A nice application. One suggestion: I would have implemented it so >> that a maximum on one backward hyperlink menu could be visible at once >> - try clicking on two RHS's and you'll get too "menus" visible at the >> same time. >> >> You also might want to mail this out on haskell-cafe - which is more >> appropriate for "general haskell" things, ghc-users is more for direct >> issues with GHC (although haskell-cafe can also be used for those) >> >> Thanks >> >> Neil >> >> On 8/16/07, Peter Hercek <peter(a)syncad.com> wrote: >>> Hi, >>> >>> I was improving my Haskell knowledge lately and I created a small dhtml application which allows browsing of >>> Haskell 98 grammar. I contains both forward and backward hyperlinks. By backward hyperlink I mean that you can >>> click on an a production head and you get a popup list box where you can navigate to any production using the >>> nonterminal. If you like it please save and use your local copy since the server cannot handle much load. >>> >>> http://www.hck.sk/users/peter/ >>> >>> Peter. >>> >>> _______________________________________________ >>> Glasgow-haskell-users mailing list >>> Glasgow-haskell-users(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users >>>

1 0