February 2009 - Beginners

Re: Majority Element
by Keith Sheppard 22 Feb '09

22 Feb '09

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" <matthewjwilliams1(a)googlemail.com> > Subject: [Haskell-beginners] Majority Element > To: beginners(a)haskell.org > Message-ID: <49a0a726.278e420a.6b19.ffffe361(a)mx.google.com> > 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 > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners >

2 1

Baffled by Parsec
by Colin Paul Adams 22 Feb '09

22 Feb '09

The tutorials I've found don't tell me what I want to know :-( I have lines that begin with an integer, then white-space, and then further structure to the end-of-line. So for a starter, could you show me how to write a parser for the integer (returning an Int), and how to combine it with a parser for the rest of the line (take that as written - it isn't, but I'll try to do that myself given such a kick-start). Thanks. -- Colin Adams Preston Lancashire

5 9

Majority Element
by Matthew J. Williams 21 Feb '09

21 Feb '09

Dear listers What is a majority element in an array? Sincerely Matthew J. Williams

2 1

Help with monads (I think...)
by Patrick LeBoutillier 21 Feb '09

21 Feb '09

Hi all, I'm trying to implement the following simple Perl program in Haskell: my $nb_tests = 0 ; sub ok { my $bool = shift ; $nb_tests++ ; print STDOUT ($bool ? "ok" : "nok") . " $nb_tests\n" ; } ok(0) ; ok(1) ; The output is: nok 1 ok 2 I'm pretty much a Haskell newbie, but I know a bit about monads (and have been reading "Real World Haskell"), and I think I need to put the ok function must live inside some kind of state monad. My problem is that I also would like the ok function to perform some IO (as shown above, print). How is a case like this handled? Can my function live in 2 monads? Thanks a lot, Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

4 3

flip lookup in ghci
by Matt R 20 Feb '09

20 Feb '09

So what's this all about then? How come a has become ()? ghci> :t lookup lookup :: (Eq a) => a -> [(a, b)] -> Maybe b ghci> :t flip lookup flip lookup :: (Eq a) => [(a, b)] -> a -> Maybe b ghci> let lookupIn = (flip lookup :: (Eq a) => [(a, b)] -> a -> Maybe b ) ghci> :t lookupIn lookupIn :: [((), b)] -> () -> Maybe b

4 4

Counting Fruits
by Adolfo Builes 20 Feb '09

20 Feb '09

Hello everyone , I wanted to do a small program which read a txt with fruit's name in each line and then print how many fruits I have of each type. something like these: apple apple and then [(apple,2)] I came up whit this import qualified Data.Map as Map import Data.List import System.IO main = do file <- readFile "fruits.txt" let answer = proccessFile $ lines file putStrLn (show answer) proccessFile :: [String] -> [(String,Int)] proccessFile file = Map.toAscList $ parseFile Map.empty file where parseFile fruits [] = fruits parseFile fruits_map (x:xs) = parseFile (Map.insertWith (+) x 1 fruits_map) xs It works, but I would like to know how would you do it ?, Share different points of view, different code. Was it a good idea to use a Map ?, Did I separate the code in a proper way, I mean pure - impure ? How can we improve the performance ? Best Regards for everyone. Adolfo

3 2

Haskell Tutorial Code Error
by Pete Ryland 20 Feb '09

20 Feb '09

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

1 0

Sequential IO processing
by Sergey V. Mikhanov 19 Feb '09

19 Feb '09

Hi community, I am making my first steps in Haskell, reading Haskell wikibook and now stuck with one of the excercises, namely this one: Implement a function sequenceIO :: [IO a] -> IO [a]. Given a list of actions, this function runs each of the actions in order and returns all their results as a list. This is what I came with: ioOne :: Num a => IO a ioOne = do print guid return guid where guid = 2 ioTwo :: Num a => IO a ioTwo = do print guid return guid where guid = 3 sequenceIO :: Num a => [IO a] -> IO [a] sequenceIO [] = return [] sequenceIO (x : xs) = do result <- x return result : sequenceIO xs First two functions are there because of the invocation that I've planned: sequenceIO [getGuid, getNextGuid]. However, this could not be compiled (GHC): Couldn't match expected type `[m a]' against inferred type `IO [a]' In the second argument of `(:)', namely `sequenceIO xs' In the expression: return result : sequenceIO xs In the expression: do result <- x return result : sequenceIO xs Fine, I thought, something wrong with the type of the 'sequenceIO xs' (becasue I am sure the type of 'result' is fine). So I wrote another program to check what happens to the result of IO action evaluation (namely, which type is assigned): bar :: Num a => IO a bar = do print guid return guid where guid = 2 foo = do result <- bar result This could not be compiled either: No instance for (Num (IO b)) arising from a use of `bar' at auxil.hs:8:19-21 Possible fix: add an instance declaration for (Num (IO b)) In a stmt of a 'do' expression: result <- bar In the expression: do result <- bar result In the definition of `foo': foo = do result <- bar result I am a newbie, so I am interpreting this like "Haskell could not construct Num from the result of invocation of bar, which is of type IO a". But why do I need this at all? When doing console I/O with 'result <- getLine', I do not need to reconstruct String from the result. What am I doing wrong? Where is the failure in reasoning? Thanks, Sergey

4 5

Re: [Haskell-cafe] Re: permuting a list
by Alberto Ruiz 17 Feb '09

17 Feb '09

Heinrich Apfelmus wrote: > Jon Fairbairn wrote: >> Heinrich Apfelmus writes: >> >>> The answer is a resounding "yes" and the main idea is that shuffling a >>> list is *essentially the same* as sorting a list; the minor difference >>> being that the former chooses a permutation at random while the latter >>> chooses a very particular permutation, namely the one that sorts the input. >>> >>> For the full exposition, see >>> >>> http://apfelmus.nfshost.com/random-permutations.html >> I haven't been following the thread, but my initial reaction >> would have been something like use System.Random.randoms to >> get a list rs and then do (roughly) >> >> randomPerm = map snd . sortBy (compare `on` fst) . zip rs >> >> How bad is that? I mean, how unfair does it get? > > It's fair, but may duplicate elements, i.e. it doesn't necessarily > create a permutation. For example, rs could be something like > > rs = [5,3,3,3,2,4] > How about using random doubles? randomPerm xs = fmap (map snd . sort . flip zip xs) rs where rs = fmap (randoms . mkStdGen) randomIO :: IO [Double]

9 10

Palindromic solution??
by Alan Cameron 16 Feb '09

16 Feb '09

>Date: Mon, 16 Feb 2009 16:32:23 +0100 >From: Miguel Pignatelli <miguel.pignatelli(a)uv.es> >Subject: [Haskell-beginners] Indentation of local functions >To: beginners(a)haskell.org >Message-ID: <90C28A9E-A67D-47CA-8416-5F1C5C27A1F9(a)uv.es> >Content-Type: text/plain; charset="us-ascii" > >Hi all, > >This is my first post in this forum, I'm pretty new to Haskell (although I >have some previous experience in functional programming with OCaml) > >I'm trying to write the typical function that determines if a list is a >palindrome. >the typical answer would be something like: > >isPalindrome xs = xs == (reverse xs) > >But I find this pretty inefficient (duplication of the list and double of >needed comparisons). >So I tried my own version using just indexes: > >isPalindrome xs = > isPalindrome' 0 (length xs) > where isPalindrome' i j = > if i == j -- line 43 > then True > else > if (xs !! i) == (xs !! (j-1)) > then isPalindrome' (i+1) (j-1) > else False > >But, when trying to load this in ghci it throws the following error: > >xxx.hs:43:12: parse error (possibly incorrect indentation) Failed, modules >loaded: none. >(Line 43 is marked in the code) > >I seems that the definition of isPalindrome' must be in one line. So, this >works as expected: > >isPalindrome xs = > isPalindrome' 0 (length xs) > where isPalindrome' i j = if i == j then True else if (xs !! i) == (xs !! (j-1)) then isPalindrome' (i+1) (j-1) else False > >Is there any way to make the local definition of isPalindrome' more >readable? > >Any help in understanding this would be appreciated > >Thanks in advance, > I have found one solution to your problem isPalindrome xs = isPalindrome' 0 (length xs) where isPalindrome' i j = if i == j -- line 43 then True else if (xs !! i) == (xs !! (j-1)) then isPalindrome' (i+1) (j-1) else False This loads without error but poses a second problem it generates an index too large exception. Alan Cameron

4 4