Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Baffled by Parsec (Felipe Lessa)
2. Re: Baffled by Parsec (Antoine Latter)
3. Re: A better way? (Heinrich Apfelmus)
4. Re: A better way? (Heinrich Apfelmus)
5. Re: Re: A better way? (Daniel Fischer)
6. Re: Majority Element (Keith Sheppard)
7. Re: Re: Majority Element (Daniel Fischer)
8. Haskell Tutorial Code Error (Pete Ryland)
9. Getting into nested monad transformers (Arthur Chan)
----------------------------------------------------------------------
Message: 1
Date: Sun, 22 Feb 2009 05:14:25 -0300
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] Baffled by Parsec
To: Colin Paul Adams <[email protected]>
Cc: [email protected], [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sun, Feb 22, 2009 at 5:02 AM, Colin Paul Adams
<[email protected]> wrote:
> Hm.
>
> It's not on my local copy of the GHC libraries documentation (ghc
> 6.10.1), although if I click the source button, I can see it.
My GHC 6.10.1 was compiled from source and Parsec comes from a
different ebuild (Gentoo), and digit isn't documented as well. It must
be some problem with parsec < 3, because Hackage has the same problem
for old Parsec[1].
[1]
http://hackage.haskell.org/packages/archive/parsec/2.1.0.1/doc/html/Text-ParserCombinators-Parsec-Char.html
--
Felipe.
------------------------------
Message: 2
Date: Sun, 22 Feb 2009 02:19:00 -0600
From: Antoine Latter <[email protected]>
Subject: Re: [Haskell-beginners] Baffled by Parsec
To: Felipe Lessa <[email protected]>
Cc: [email protected], [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On Sun, Feb 22, 2009 at 2:14 AM, Felipe Lessa <[email protected]> wrote:
>
> My GHC 6.10.1 was compiled from source and Parsec comes from a
> different ebuild (Gentoo), and digit isn't documented as well. It must
> be some problem with parsec < 3, because Hackage has the same problem
> for old Parsec[1].
>
> [1]
> http://hackage.haskell.org/packages/archive/parsec/2.1.0.1/doc/html/Text-ParserCombinators-Parsec-Char.html
>
>From the sources:
> upper, lower, alphaNum, letter, digit, hexDigit, octDigit :: CharParser st
> Char
I think I've seen Haddock have trouble documenting declarations which
share a type signature in other places, as well.
Antoine
------------------------------
Message: 3
Date: Sun, 22 Feb 2009 15:30:55 +0100
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: A better way?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Daniel Fischer wrote:
>
> Yes, foldr was the wrong choice. make it foldl' (don't forget the prime at
> the
> end) and it works for large tables. If the rows are short, it actually is
> faster (here) than your version, but if the rows are long , e.g.
>
> maxTableColumnWidths (replicate 2000 (replicate 1000 "what?"))
>
> your version is faster than
>
> import Data.List (foldl')
>
> seqList [] = False
> seqList (head:tail)
> | head `seq` False = undefined
> | otherwise = seqList tail
>
> evalList xs
> | seqList xs = undefined
> | otherwise = xs
>
> zipWithD :: (a -> a -> a) -> [a] -> [a] -> [a]
> zipWithD f (x:xt) (y:yt) = f x y:zipWithD f xt yt
> zipWithD _ [] ys = ys
> zipWithD _ xs [] = xs
>
> maxTableColumnWidths =
> foldl' ((evalList .) . zipWithD max) [] . map (map length)
Nice! I'd use bang patterns in favor of the now outdated
| x `seq` False = undefined
pattern though.
Actually, I'd use
import Control.Parallel.Strategies
maxWidths = foldl' (\xs ys -> zipWithD max xs ys `using` rnf) []
. map (map length)
The module quite useful for controlling evaluation, even when no
parallelism is involved.
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 4
Date: Sun, 22 Feb 2009 15:34:49 +0100
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: A better way?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Patrick LeBoutillier wrote:
> Hi,
>
> I changed my code to :
>
> maxTableColumnWidths :: [[String]] -> [Int]
> maxTableColumnWidths = foldl' rowMax zeros
> where rowMax = zipWith (\m f -> max (length f) m)
> zeros = 0 : zeros
>
> but it still blows the stack. I don't understand why. Doesn't foldl'
> force the evaluation of each call to rowMax? If so then I don't see
> what causes the stack to get so big... unless I'm looking in the wrong
> place...
>
> Can anyone shed some light?
It does force the evaluation of each call to rowMax but only to weak
head normal form. In other words, it will only evaluate the list to
either a cons cell or an empty list
blah ---> blah : blah
\-> []
See also
http://en.wikibooks.org/wiki/Haskell/Graph_reduction
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 5
Date: Sun, 22 Feb 2009 16:17:24 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: A better way?
To: Heinrich Apfelmus <[email protected]>,
[email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Sonntag, 22. Februar 2009 15:30 schrieb Heinrich Apfelmus:
> Daniel Fischer wrote:
> > Yes, foldr was the wrong choice. make it foldl' (don't forget the prime
> > at the end) and it works for large tables. If the rows are short, it
> > actually is faster (here) than your version, but if the rows are long ,
> > e.g.
> >
> > maxTableColumnWidths (replicate 2000 (replicate 1000 "what?"))
> >
> > your version is faster than
> >
> > import Data.List (foldl')
> >
> > seqList [] = False
> > seqList (head:tail)
> >
> > | head `seq` False = undefined
> > | otherwise = seqList tail
> >
> > evalList xs
> >
> > | seqList xs = undefined
> > | otherwise = xs
> >
> > zipWithD :: (a -> a -> a) -> [a] -> [a] -> [a]
> > zipWithD f (x:xt) (y:yt) = f x y:zipWithD f xt yt
> > zipWithD _ [] ys = ys
> > zipWithD _ xs [] = xs
> >
> > maxTableColumnWidths =
> > foldl' ((evalList .) . zipWithD max) [] . map (map length)
>
> Nice! I'd use bang patterns in favor of the now outdated
>
> | x `seq` False = undefined
>
> pattern though.
I would, too, but they're not yet portable, are they?
Which implementations other than GHC currently support them?
And since seqList was already there, I used that.
>
>
> Actually, I'd use
>
> import Control.Parallel.Strategies
>
> maxWidths = foldl' (\xs ys -> zipWithD max xs ys `using` rnf) []
> . map (map length)
>
> The module quite useful for controlling evaluation, even when no
> parallelism is involved.
Winner!
>
>
> Regards,
> apfelmus
>
Cheers,
Daniel
------------------------------
Message: 6
Date: Sun, 22 Feb 2009 11:12:19 -0500
From: Keith Sheppard <[email protected]>
Subject: [Haskell-beginners] Re: Majority Element
To: [email protected], [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
I think this gets you what you want:
majority nums = find (\x -> fromIntegral (length x) > (fromIntegral
(length nums)) / 2) (group(sort(nums)))
It returns a "Maybe" list containing all majority elements. Something
that avoids the sort would be faster though.
-Keith
> Message: 8
> Date: Sun, 22 Feb 2009 01:15:30 +0000
> From: "Matthew J. Williams" <[email protected]>
> Subject: [Haskell-beginners] Majority Element
> To: [email protected]
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset="us-ascii"; format=flowed
>
> Dear listers
>
> What is a majority element in an array?
>
> Sincerely
> Matthew J. Williams
>
>
>
> ------------------------------
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 7
Date: Sun, 22 Feb 2009 18:39:29 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: Majority Element
To: Keith Sheppard <[email protected]>, [email protected],
[email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Sonntag, 22. Februar 2009 17:12 schrieb Keith Sheppard:
> > Message: 8
> > Date: Sun, 22 Feb 2009 01:15:30 +0000
> > From: "Matthew J. Williams" <[email protected]>
> > Subject: [Haskell-beginners] Majority Element
> > To: [email protected]
> > Message-ID: <[email protected]>
> > Content-Type: text/plain; charset="us-ascii"; format=flowed
> >
> > Dear listers
> >
> > What is a majority element in an array?
> >
> > Sincerely
> > Matthew J. Williams
> >
The answer is implicit in Keith's code below, but let's state it also in plain
text:
A majority element in a collection C of n things is a value that appears
strictly more than n/2 times in C.
In general, no majority element exists.
I had never met the term before Matthew's post. Does anybody know for what it
is important?
> I think this gets you what you want:
>
> majority nums = find (\x -> fromIntegral (length x) > (fromIntegral
> (length nums)) / 2) (group(sort(nums)))
You don't need the fromIntegral here, integer division does the right thing.
In case a majority element a exists, this returns Just [a,a...], so you might
add an "fmap head" to get the element itself.
>
> It returns a "Maybe" list containing all majority elements. Something
> that avoids the sort would be faster though.
Not the naive algorithm. However, if the type of elements doesn't belong to
Ord, we can't use sort :(
>
> -Keith
>
findMajority :: Eq a => [a] -> Maybe a
findMajority [] = Nothing
findMajority xxs@(x:xs) = case sweep x 1 xs of
Nothing -> Nothing
Just candidate -> verify candidate 0 xxs
where
sweep a count []
| count == 0 = Nothing
| otherwise = Just a
sweep _ 0 (y:ys) = sweep y 1 ys
sweep a count (y:ys)
| a == y = sweep a (count+1) ys
| otherwise = sweep a (count-1) ys
verify c count (y:ys)
| c == y = verify c (count+1) ys
| otherwise = verify c (count-1) ys
verify c count []
| count > 0 = Just c
| otherwise = Nothing
Cheers,
Daniel
------------------------------
Message: 8
Date: Fri, 20 Feb 2009 11:02:03 +0100
From: Pete Ryland <[email protected]>
Subject: [Haskell-beginners] Haskell Tutorial Code Error
To: [email protected], [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi,
Sorry to post to a list, but there are no other contact addresses on
the haskell.org site or in the tutorial itself. Any replies, please
also CC me as I do not subscribe to any haskell.org lists.
I noticed an error in the Haskell Tutorial in section 8.3. The code
for the Tree parser will not work. Specifically, the following is
broken:
readsTree :: (Read a) => ReadS (Tree a)
readsTree s = [(Branch l r, x) | ("<", t) <- lex s,
(l, u) <- readsTree t,
("|", v) <- lex u,
(r, w) <- readsTree v,
(">", x) <- lex w ]
++
[(Leaf x, t) | (x, t) <- reads s ]
It will not read a string like "<<1|2>|3>" because of the "<<" which
the lexer will see as one token. Here is another implementation:
showsTree :: (Show a) => Tree a -> ShowS
showsTree (Leaf x) = ("Leaf " ++) . shows x
showsTree (Branch l r) = ("Branch (" ++) . showsTree l . (") (" ++)
. showsTree r . (')':)
readsTree :: (Read a) => ReadS (Tree a)
readsTree s = [(Branch l r, v) | ("Branch", t) <- lex s,
(l, u) <- readsTree t,
(r, v) <- readsTree u ]
++
[(Leaf x, u) | ("Leaf", t) <- lex s,
(x, u) <- reads t ]
++
[(x, v) | ("(", t) <- lex s,
(x, u) <- readsTree t,
(")", v) <- lex u ]
instance Show a => Show (Tree a) where
showsPrec _ x = showsTree x
instance Read a => Read (Tree a) where
readsPrec _ s = readsTree s
This is almost equivalent to the derived one, but will accept strings
like "Branch Leaf 3 Branch Branch Leaf 1 Leaf 2 Branch Leaf 5 Leaf 4"
(that is, without the parentheses).
Regards,
Pete
------------------------------
Message: 9
Date: Thu, 19 Feb 2009 21:51:06 -0800
From: Arthur Chan <[email protected]>
Subject: [Haskell-beginners] Getting into nested monad transformers
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="utf-8"
Hey all,
I've been trying to access the inner state "s" for this type:
newtype TestThingey s a = TestThingey {
runTrans :: ReaderT Int (StateT String (StateT s IO)) a
} deriving (Monad, MonadIO, MonadState String, MonadReader Int)
It doesn't seem to be doable. I could make it into a regular type
declaration, but then I lose the GeneralizedNewtypeDeriving. Is this
common? Or do people just avoid needing to use "lift"?
-Arthur
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090219/fae704c3/attachment.htm
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 21
****************************************
