October 2005 - Haskell-Cafe

RE: [Haskell-cafe] lockFile: fd out of range
by Simon Marlow 27 Oct '05

27 Oct '05

On 25 October 2005 17:02, Joel Reymont wrote: > Is there a set limit on the number of file descriptors that a Haskell > program can open? > > I'm using hs-plugins on FreeBSD to transparently compile, load and > launch scripts that establish a connection to a server. I'm getting > this error: > > internal error: lockFile: fd out of range > Please report this as a bug to glasgow-haskell-bugs(a)haskell.org, > or http://www.sourceforge.net/projects/ghc/ lockFile uses FD_SETSIZE as its idea of the maximum value of a file descriptor. If you can get file descriptors outside this range, then the above error would ensue. Not sure if this is the case on FreeBSD... seems odd if it is. Can you try a truss/ktrace and see the values of your file descriptors? Cheers, Simon

2 1

RE: Instances That Ignore Type Constraints? (HList-related)
by Ralf Lammel 27 Oct '05

27 Oct '05

Yeah, I was also thinking of impredicative types and that they would make this problem go away. First of all, we may need to wait a while for such types to become available in Haskell, but Daan has good stuff at avail. Also, for clarity, let me just point out that this is really about an *interaction* of impredicativeness *and* type classes. Hence, I really think that an argument in favor of impredicative types is slightly overrated unless a Haskell approach to impredicativeness is fully conclusive for the type-class story. The following queries make it clear: Prelude> null [fromEnum] <interactive>:1:6: Ambiguous type variable `a' in the constraint: `Enum a' arising from use of `fromEnum' at <interactive>:1:6-13 Probable fix: add a type signature that fixes these type variable(s) Prelude> null [id] False More importantly, I need more input to fully endorse the appropriateness of impredicative types in this sort of context. That is, the question is ... what does it *mean* to wrap (or to box or to cartoon) an expression with non-escaping type variables that locally occur in type-class constraints? GHC/Haskell, as of today: - it means nothing; type error. Some sort of impredicative type: - it means universal quantification Potentially elsewhere: - it means existential quantification In Ghc with incoherent instances: - see above; except that the instance is actually selected. In addition to this scary diversity, all the three last choices are bogus in some sense because the quantified variables are totally inaccessible; so why would a type system honor such potentially accidental opaqueness. In summary, this makes me conclude that null [fromEnum] is just a really loose question to ask, which is perhaps just better rejected by a strong type system, no? Please, prove that I am wrong. :-) Ralf Oleg wrote: > When GHC does implement > MLF and start explicitly supporting impredicative types, the problem > would be fixed indeed... Currently, the only way to achieve the same > effect is to do this manually: > > newtype W = W (forall a. (Enum a) => a -> Int) > > *Main> null [W fromEnum] > False > > Perhaps indeed we should move to Cafe...

1 0

Nice way to calculate character frequency in a string
by Charles SDudu 27 Oct '05

27 Oct '05

Hello, I need to calculate the frequency of each character in a String. And if I can do this really well in C, I dont find a nice (and fast) answer in haskell. I tried several functions, listed below, and even the fastest do a lot of unnecessary things : calc :: String -> [ (Char, Int) ] -- 3.0s normally (without profiling) -- time 10-12% alloc 59% (info from profiling) -- so it's the fastest when I profile but not when I compile normally -- mutable array may be better but it's to complicated for me calc = filter (\p -> snd p > 0) . assocs . foldl (\k c -> unsafeReplace k [(fromEnum c, (unsafeAt k (fromEnum c))+1)] ) k where k = array (toEnum 0, toEnum 255) [(toEnum i, 0) | i <- [0 .. 255]] :: UArray Char Int -- 2.1s normally -- time 15-19% alloc 40% (info from profiling) -- so for true, it's the best but the sort and group probably do unnecessary things calc s = map (\l -> (head l, length l)) $ group $ sort s -- 3.4s normally -- time 58% alloc 0% (info from profiling) -- this one dont do unnecessary things but has to read the file again for each character -- calc s = map (\c -> (c, foldl (\a b -> if b==c then a+1 else a) 0 s)) $ nub s -- 22s normally -- time 85% alloc 92% (info from profiling) -- this one read the file only one time but is really slow calc = foldl (addfreq) [] where addfreq f c = let xs1 = takeWhile (\f -> fst f /= c) f xs2 = dropWhile (\f -> fst f /= c) f xs = if null xs2 then [(c,1)] else ((fst . head) xs2, (snd . head) xs2 + 1) : tail xs2 in xs1 ++ xs -- I have a lot of even slower version but I wont include them -- each compilation was done with GHC 6.4.1 with the -O flag and with -O -prof -auto-all for profiling Thanks for your answer, Charles PS : Yes, english is not my mother language... :-(

7 6

Re: Typeclasses and GADT [Was: Regular Expressions without GADTs]
by oleg＠pobox.com 27 Oct '05

27 Oct '05

Tomasz Zielonka wrote: > Speaking about casts, I was playing with using GADTs to create a > non-extensible version of Data.Typeable and Data.Dynamic. > I wonder if it's possible to write such a thing without GADTs (and > unsafeCoerce, which is used in Data.Dynamic, IIRC). Absolutely. Stephanie Weirich did that back in 2000 (actually, earlier: her paper, TypeSafe cast was presented at ICFP'00). The code does not use existentials -- only universals. BTW, if you don't plan to store your dynamics in a data structure (or plan to cast them to the same thing), then no explicit quantification is needed and the code becomes Haskell98. Here's her code for the cast, with slight embellishments. It should be pointed out that we can cast polymorphic lists and polymorphic functions. There is a different way to perform casting within a closed universe, see http://www.mail-archive.com/haskell@haskell.org/msg13089.html {-# OPTIONS -fglasgow-exts #-} module CWeirich where class CF a where cast :: CT b => a -> Maybe b class CT b where cBool :: Bool -> Maybe b cBool = const Nothing cInt :: Int -> Maybe b cInt = const Nothing cList :: CF a => [a] -> Maybe b cList = const Nothing cFun :: (CT b1, CF a2) => (b1->a2) -> Maybe b cFun = const Nothing instance CF Bool where cast = cBool instance CF Int where cast = cInt instance CF a => CF [a] where cast = cList instance (CT b1, CF a2) => CF (b1->a2) where cast = cFun instance CT Bool where cBool = Just instance CT Int where cInt = Just instance CT b => CT [b] where cList x = mapM cast x instance (CT b2, CF a1) => CT (a1->b2) where cFun f = let f' :: a1 -> Maybe b2 f' x = maybe Nothing (cast . f) (cast x) f'' x = maybe undefined id (f' x) in maybe Nothing (const $ Just f'') (f' undefined) -- This is a universal rather than existential type! data Dyn = Dyn {fromDyn :: forall b. CT b => Maybe b} toDyn :: CF a => a -> Dyn toDyn a = Dyn (cast a) td1 = toDyn True td2 = toDyn [1::Int, 2,3] td3 = toDyn not tf1 = fromDyn td1 :: Maybe Bool tf2 = fromDyn td1 :: Maybe Int tf3 = fromDyn td2 :: Maybe [Int] tf4 :: Maybe Bool = maybe Nothing (\f -> Just $ f True) (fromDyn td2) tf5 :: Maybe Bool = maybe Nothing (\f -> Just $ f True) (fromDyn td3) tf6 :: Maybe Int = maybe Nothing (\f -> Just $ f True) (fromDyn td3)

2 1

Regular Expressions without GADTs
by oleg＠pobox.com 26 Oct '05

26 Oct '05

Conor McBride wrote: > Inspired by Ralf's post, I thought I'd just GADTize a dependently typed > program I wrote in 2001. Equally inspired, I thought of deGADTizing that code. The code below also uses no existentials, and no local type annotations. The code is more general in that the parser works in an arbitrary MonadPlus. If that happens to be the List monad, we can see alternative parses. The tests illustrate alternative parses and parsing of a list of integers, for example. The code seems a bit simpler, too. {-# OPTIONS -fglasgow-exts #-} module RX where import Control.Monad -- If monadPlus is List, we can get alternative parses class RegExp t tok a | t tok -> a where parse :: MonadPlus m => t -> [tok] -> m a data Zero = Zero data One = One newtype Check tok = Check (tok -> Bool) data Plus r1 r2 = Plus r1 r2 data Mult r1 r2 = Mult r1 r2 data Push tok r = Push tok r newtype Star r = Star r data Void = Void -- Parser Zero fails everywhere instance RegExp Zero tok Void where parse _ _ = mzero -- Parser One recognizes the empty string instance RegExp One tok () where parse _ [] = return () parse _ _ = mzero -- Parser (Check p) recognizes a single-element stream [tok] -- provided tok satisfies the predicate p instance RegExp (Check tok) tok tok where parse (Check p) [t] | p t = return t parse _ _ = mzero -- Parser (Push tok r) prepends tok to the stream and gets parser -- r to recognize the result instance RegExp r tok a => RegExp (Push tok r) tok a where parse (Push tok r) ts = parse r (tok:ts) -- Non-deterministic choice of parsers r1 and r2, applied to the same stream instance (RegExp r1 tok a, RegExp r2 tok b) => RegExp (Plus r1 r2) tok (Either a b) where parse (Plus r1 r2) ts = (liftM Left $ parse r1 ts) `mplus` (liftM Right $ parse r2 ts) -- Mult r1 r2: A sequence of parsers r1 and r2. -- Note the order: we search for the longest prefix of the input stream -- that satisfies the parser r1 instance (RegExp r1 tok a, RegExp r2 tok b) => RegExp (Mult r1 r2) tok (a, b) where parse (Mult r1 r2) ts@[] = liftM2 (,) (parse r1 ts) (parse r2 ts) parse (Mult r1 r2) (t:ts) = parse (Mult (Push t r1) r2) ts `mplus` liftM2 (,) (parse r1 ([] `asTypeOf` ts)) (parse r2 (t:ts)) -- Kleene's star instance RegExp r tok a => RegExp (Star r) tok [a] where parse (Star r) [] = return [] parse (Star r) ts = parse (Mult r (Star r)) ts >>= (\ (x,xs) -> return $ x:xs) p1 = (Mult (Star (Check (== 'a'))) (Star (Check (== 'b')))) asMayBe :: Maybe a -> Maybe a asMayBe = id asList :: [a] -> [a] asList = id testp = asMayBe $ parse (Star (Mult (Star (Check (== 'a'))) (Star (Check (== 'b'))))) "abaabaaabbbb" -- *RX> testp -- Just [("a","b"),("aa","b"),("aaa","bbbb")] -- see alternative parses testp1 = take 3 $ asList $ parse (Star (Mult (Star (Check (== 'a'))) (Star (Check (== 'b'))))) "abaabaaabbbb" -- Parsing the list of integers ieven = even :: Int->Bool iodd = odd :: Int->Bool p2 = Plus (Mult (Check iodd) (Mult (Check iodd) (Star (Check ieven)))) (Mult (Check ieven) (Star (Check iodd))) -- the parser is ambiguous. We can see the alternatives test2 = take 3 $ asList $ parse (Star p2) [1::Int,1,2,3,3,4]

8 10

Re: [Fwd: Re: [Haskell-cafe] Typeclasses and GADT [Was: Regular Expressions without GADTs]]
by kahl＠cas.mcmaster.ca 26 Oct '05

26 Oct '05

Tomasz Zielonka <tomasz.zielonka(a)gmail.com> wrote Wed, 26 Oct 2005 13:37:29 +0200: > > Speaking about casts, I was playing with using GADTs to create a > non-extensible version of Data.Typeable and Data.Dynamic. > I wonder if it's possible to write such a thing without GADTs (and > unsafeCoerce, which is used in Data.Dynamic, IIRC). It is possible to get even closer to Typeable by using the same interface --- which is sufficient for some applications. Otherwise, what I did recently is essentially equivalent to the ``non-Dynamic part'' of Tomasz code (and adding Dyn would of course work in the same way): Thomasz' --> attached modules ------------------------------------------------------- data Type --> data TI.TI* class Typed --> class Typeable.Typeable* newtype Wrapper* --> replaced by the ``*''s above ;-) Wolfram --[[application/octet-stream Content-Disposition: attachment; filename="TI.lhs"][quoted-printable]] %include lhs2TeX.fmt %include WKlhs.sty \section{Type Indices} %{-# OPTIONS_GHC -fglasgow-exts #-} taken out for lhs2tex \begin{code} module TI where import NatNum \end{code} For each ground type |a| constructed only from supported type constructors, there is exactly one \emph{type index} in |TI a|. In that respect, an element of |TI a| is similar to the satisfaction of the constraint |Typeable a|. The important difference between |TI a| and |Typeable a| is that structural induction over the structure of a type documented by a |TI a| contains references to the constituent types \emph{at the type level}, while structural induction over |TypeRep| representations of type structure made accessible by |Typeable a| has no connection to the type level at all. \begin{code} data TI :: * -> * where Triv :: TI () Bool :: TI Bool Char :: TI Char Nat :: TI Nat Int :: TI Int Integer :: TI Integer Float :: TI Float Double :: TI Double Apply_0 :: TI_0 t -> TI a -> TI (t a) Apply_1 :: TI_1 t -> TI_0 a -> TI (t a) \end{code} Since one of the limitations of |Data.Typeable| is its naming scheme that does not accommodate higher-kinded type constructors, we use a naming scheme that is at least somewhat open in that direction, and provide alternative names following the scheme of |Data.Typeable| as type synonyms. \begin{code} type TI1 = TI_0 type TI2 = TI_0_0 type TI3 = TI_0_0_0 \end{code} \begin{code} data TI_0 :: (* -> *) -> * where Maybe :: TI_0 Maybe List :: TI_0 [] Apply_0_0 :: TI_0_0 t -> TI a -> TI_0 (t a) \end{code} \begin{code} data TI_0_0 :: (* -> * -> *) -> * where Either :: TI_0_0 Either Pair :: TI_0_0 (,) Fct :: TI_0_0 (->) Apply_0_0_0 :: TI_0_0_0 t -> TI a -> TI_0_0 (t a) \end{code} \begin{code} data TI_0_0_0 :: (* -> * -> * -> *) -> * where Tup3 :: TI_0_0_0 (,,) \end{code} Just to demonstrate a higher-order kind in this context, we define the datatype recursion type constructor. \begin{code} data TI_1 :: ((* -> *) -> *) -> * where Fix :: TI_1 DFix data DFix f = DFix (f (DFix f)) \end{code} Defining type index equality without requiring identical types makes the implementation of the cast functions much easier. \begin{code} eqTI :: TI a -> TI b -> Bool eqTI Triv Triv = True eqTI Bool Bool = True eqTI Char Char = True eqTI Nat Nat = True eqTI Int Int = True eqTI Integer Integer = True eqTI Float Float = True eqTI Double Double = True eqTI (Apply_0 t a) (Apply_0 t' a') = eqTI_0 t t' && eqTI a a' eqTI (Apply_1 t a) (Apply_1 t' a') = eqTI_1 t t' && eqTI_0 a a' eqTI _ _ = False \end{code} \begin{code} eqTI_0 :: TI_0 t -> TI_0 t' -> Bool eqTI_0 Maybe Maybe = True eqTI_0 List List = True eqTI_0 (Apply_0_0 t a) (Apply_0_0 t' a') = eqTI_0_0 t t' && eqTI a a' eqTI_0 _ _ = False \end{code} \begin{code} eqTI_1 :: TI_1 t -> TI_1 t' -> Bool eqTI_1 Fix Fix = True eqTI_1 _ _ = False \end{code} \begin{code} eqTI_0_0 :: TI_0_0 t -> TI_0_0 t' -> Bool eqTI_0_0 Either Either = True eqTI_0_0 Pair Pair = True eqTI_0_0 Fct Fct = True eqTI_0_0 _ _ = False \end{code} %{{{ EMACS lv % Local Variables: % folded-file: t % fold-internal-margins: 0 % eval: (fold-set-marks "%{{{ " "%}}}") % eval: (fold-whole-buffer) % end: %}}} --[[application/octet-stream Content-Disposition: attachment; filename="Typeable.lhs"][quoted-printable]] %include lhs2TeX.fmt %include WKlhs.sty \section{Home-made |Typeable|} %{-# OPTIONS_GHC -fglasgow-exts #-} taken out for lhs2tex \begin{code} module Typeable where import NatNum import TI import GHC.Base ( unsafeCoerce# ) \end{code} This module is currently happily restricting itself to Glasgow Haskell. Many things that are done in a more portable way in |Data.Typeable| are done in a more concise, but GHC-specific way here. The following function is GHC-specific: \begin{code} unsafeCoerce :: a -> b unsafeCoerce = unsafeCoerce# \end{code} For the tyme being, we only go to |Typeable3|, while |Data.Typeable| goes all the way to |Typeable7|. \begin{code} class Typeable a where typeIndex :: a -> TI a class Typeable1 t where typeIndex1 :: t a -> TI1 t class Typeable2 t where typeIndex2 :: t a b -> TI2 t class Typeable3 t where typeIndex3 :: t a b c -> TI3 t \end{code} We shamelessly use scoped type variables to abbreviate the |cast| and |gcast| definitions, which otherwise correspond directly to those from |Data.Typeable|. \begin{code} cast :: (Typeable a, Typeable b) => a -> Maybe b cast x :: Maybe b = if typeIndex x `eqTI` typeIndex (undefined :: b) then Just $ unsafeCoerce x else Nothing \end{code} \begin{code} gcast :: (Typeable a, Typeable b) => c a -> Maybe (c b) gcast (x :: c a) :: Maybe (c' b) = if typeIndex (undefined :: a) `eqTI` typeIndex (undefined :: b) then Just $ unsafeCoerce x else Nothing \end{code} \begin{code} gcast1 :: (Typeable1 t, Typeable1 t') => c (t a) -> Maybe (c (t' a)) gcast1 (x :: c (t a)) :: Maybe (c' (t' a')) = if typeIndex1 (undefined :: t a) `eqTI_0` typeIndex1 (undefined :: t' a) then Just $ unsafeCoerce x else Nothing \end{code} \begin{code} gcast2 :: (Typeable2 t, Typeable2 t') => c (t a b) -> Maybe (c (t' a b)) gcast2 (x :: c (t a b)) :: Maybe (c' (t' a' b')) = if typeIndex2 (undefined :: t a b) `eqTI_0_0` typeIndex2 (undefined :: t' a b) then Just $ unsafeCoerce x else Nothing \end{code} %{{{ automatic instances For the automatic instances, the machinery from |Data.Typeable| can easily be adapted. \begin{code} instance (Typeable1 s, Typeable a) => Typeable (s a) where typeIndex = typeIndexDefault instance (Typeable2 s, Typeable a) => Typeable1 (s a) where typeIndex1 = typeIndex1Default instance (Typeable3 s, Typeable a) => Typeable2 (s a) where typeIndex2 = typeIndex2Default \end{code} \begin{code} -- | For defining a 'Typeable' instance from any 'Typeable1' instance. typeIndexDefault :: (Typeable1 t, Typeable a) => t a -> TI (t a) typeIndexDefault (x :: t a) = typeIndex1 x `Apply_0` typeIndex (undefined :: a) -- | For defining a 'Typeable1' instance from any 'Typeable2' instance. typeIndex1Default :: (Typeable2 t, Typeable a) => t a b -> TI_0 (t a) typeIndex1Default (x :: t a b) = typeIndex2 x `Apply_0_0` typeIndex (undefined :: a) -- | For defining a 'Typeable2' instance from any 'Typeable3' instance. typeIndex2Default :: (Typeable3 t, Typeable a) => t a b c -> (TI_0_0 (t a)) typeIndex2Default (x :: t a b c) = typeIndex3 x `Apply_0_0_0` typeIndex (undefined :: a) \end{code} %}}} %{{{ standard library instances With our standard library instances we are obviously restricted to the types covered by |TI|. \begin{code} instance Typeable () where typeIndex _ = Triv instance Typeable Bool where typeIndex _ = Bool instance Typeable Char where typeIndex _ = Char instance Typeable Nat where typeIndex _ = Nat instance Typeable Int where typeIndex _ = Int instance Typeable Integer where typeIndex _ = Integer instance Typeable Float where typeIndex _ = Float instance Typeable Double where typeIndex _ = Double instance Typeable1 Maybe where typeIndex1 _ = Maybe instance Typeable1 [] where typeIndex1 _ = List instance Typeable2 Either where typeIndex2 _ = Either instance Typeable2 (,) where typeIndex2 _ = Pair instance Typeable2 (->) where typeIndex2 _ = Fct \end{code} %}}} %{{{ EMACS lv % Local Variables: % folded-file: t % fold-internal-margins: 0 % eval: (fold-set-marks "%{{{ " "%}}}") % eval: (fold-whole-buffer) % end: %}}} --[[application/octet-stream Content-Disposition: attachment; filename="GCast.lhs"][quoted-printable]] %include lhs2TeX.fmt %include WKlhs.sty \section{Minimal Interface Providing Generic Cast} This module provides a minimal interface to |gcast| since this is all that is really required by many applications of |Typeable| and friends. Isolating this interface makes it easier to switch between different implementations. %{-# OPTIONS_GHC -fglasgow-exts #-} taken out for lhs2tex \begin{code} module GCast ( Typeable() , Typeable1() , Typeable2() , Typeable3() , cast , gcast , gcast1 , gcast2 ) where -- import Data.Typeable import Typeable \end{code} %{{{ EMACS lv % Local Variables: % folded-file: t % fold-internal-margins: 0 % eval: (fold-set-marks "%{{{ " "%}}}") % eval: (fold-whole-buffer) % end: %}}} --[[application/octet-stream Content-Disposition: attachment; filename="NatNum.lhs"][quoted-printable]] \section{Inductive Definition of Natural Numbers} \begin{code} module NatNum where import Data.Typeable data Nat = Zero | Succ deriving Typeable \end{code}

2 2

RE: [Haskell-cafe] Help using QuickCheck
by Simon Peyton-Jones 26 Oct '05

26 Oct '05

I'm afraid this fix didn't make it into the 6.4 branch, but the double error (which is bad) is certainly fixed in the HEAD Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | Andrew Pimlott | Sent: 21 October 2005 20:45 | To: haskell-cafe(a)haskell.org | Subject: Re: [Haskell-cafe] Help using QuickCheck | | On Fri, Oct 21, 2005 at 09:09:41PM +0200, Benjamin Franksen wrote: | > Many thanks! I wish I had remembered that I had this kind of problem | > before: ghc reports two errors, of which the /second/ one is the 'real' | > problem and the first one is just a by-product. | | The case in your original message is particularly annoying, but at least | it only affects ghci. I thought it had been fixed[1], but it is still | present in 6.4.1, so perhaps it's waiting for 6.5? | | > This practically never | > happens with C compilers which I (must, sadly) use every day and thus I | > always tend to disregard all error messages but the first. | | I generally find that most of GHC's errors are real, ie they don't | change much when I fix earlier errors. (It seems to report only one | error per function to achieve that?) It's fun to work through the dozen | reported mistakes, then compile again to see how many I actually fixed. | :-) | | Andrew | | [1] | http://sourceforge.net/tracker/index.php?func=detail&aid=1156554&group_i d=8032&atid=108032 | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

RE: [Haskell-cafe] Template Haskell -- Bug?
by Simon Peyton-Jones 26 Oct '05

26 Oct '05

| $ ghc --make THTest1.hs | Chasing modules from: THTest1.hs | Compiling THTest1TH ( ./THTest1TH.hs, ./THTest1TH.o ) | Compiling THTest1 ( THTest1.hs, THTest1.o ) | | THTest1.hs:10:4: `incrSelf' is not a (visible) method of class `IncrSelf' I've now fixed this bug, in the HEAD. The fix will appear in 6.4.2 (if we release that). Thanks for reporting it. Simon

1 0

Fwd: [Haskell-cafe] Parsing in Practice
by Tomasz Zielonka 26 Oct '05

26 Oct '05

[Sending it again to haskell-cafe] On 10/18/05, Tom Hawkins <tom(a)confluent.org> wrote: > I am writing a parser for a big, ugly, standard language and I need to > decide between using either Happy or Parsec. I wrote a parser for a big, ugly, non-standard language - Transact-SQL from MSSQL. > I currently have a priliminary LALR(1) grammar, so a port to Happy would > be relatively easy. In such situation I would try Happy first, but with some cautiousness. I also started with LALR(1) parsing in ocamlyacc, but I didn't manage to cover the whole language with this approach. The more productions I added the more conflicts I had. Of course I tried to remove the conflicts, but often when I added new productions I had to repeat the work. It is possible that my understanding of LALR parsing was insufficient, but the problem is that the set of LALR grammars is not closed under composition (as I've read in some paper on GLR parsing). Do you know that Happy supports GLR parsing? > But, I'm wondering if life would be easier if I chose Parsec's combinator > parsing instead. >From my experience it was indeed quite nice. However, there were some parts of the grammer that I didn't know how to handle without using "try", which could result in worse efficiency and error reporting. > It's error reporting seems to be top notch So long as you can avoid using "try" for non-terminals. > and it's "optional", "many", and "sepBy1" combinators are very elegant. Indeed they are, as they correspond nicely to E in EBNF ;-) > However, I have a few concerns with Parsec. First is performance; what > factor of slow-down should I expect? I only have a Parsec parser, so I can't compare. I dimly remember that my parser had an average efficiency, ie. it could parse about 100kB per second on P3 850. There is a parser-combinator version of a parser for Haskell which you could compare to the one from GHC. > Second is bug prevention. I don't have much experience writing LL(n) > grammars, so how easy is it to introduce bugs in a Parsec grammar? I always feared that this would be a problem, but it wasn't. I used a sample of about 1MB of application code to test, and I didn't get to using QuickCheck. > Even though I hate debugging LALR(1) parsing ambiguities, > it prevents problems. Yes, when you fight the conflicts, you get static guarantees in return. I wonder how it is with GLR? Best regards Tomasz

2 1

Re: [Haskell-cafe] Nice way to calculate character frequency in a string
by Charles SDudu 25 Oct '05

25 Oct '05

It seems like the fastest way to build a list of frequency from a string is this : import Data.Array (assocs, accumArray, Array) frequency :: String -> [(Char,Int)] frequency = filter (\f -> snd f>0) . assocs . accumArray (+) 0 ('\0', '\255') . map (\x->(x,1)) -- (~1.3 sec on a string of 700ko) But if we want to make this polymorphic we have to do this : import Data.Ix (Ix) frequency :: (Ix a, Bounded a) => [a] -> [(a,Int)] frequency = filter (\f -> snd f>0) . assocs . accumArray (+) 0 (minBound, maxBound) . map (\x->(x,1)) -- (>5 sec on a string of 700ko) but it's really much slower, it seems like min/maxBound are check each time or I dont know, and it's restrictive on the type of the elements of the list. The best polymorphic version seems to be : import Data.Map as Map (lookup, assocs, empty, insertWith) frequency :: (Ord a) => [a] -> [(a,Int)] frequency xs = Map.assocs $ foldl f Map.empty xs where f m x = let m' = Map.insertWith (+) x 1 m Just v = Map.lookup x m' in seq v m' -- (~2.1 sec on a string of 700ko) Which is not as fast as the specialized version on string, but really faster and less restrictive than the second. Thanks everyone for all your answers ! Charles

3 2