May 2011 - Beginners - Haskell.org

Extension for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell
by KC 21 May '11

21 May '11

Extension for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- module SelectionProblem where import Data.Array import Data.List ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- Question: is there a way to get the type signature as the following: -- smallest :: (Ord a) => Int -> [Array Int a] -> a ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- Works on 2 finite ordered disjoint sets represented as sorted arrays. smallest :: (Ord a) => Int -> (Array Int a, Array Int a) -> a smallest k (xa,ya) = search k (xa,ya) (0,m+1) (0,n+1) where (0,m) = bounds xa (0,n) = bounds ya -- Removed some of the "indexitis" at the cost of calling another function. search :: (Ord a) => Int -> (Array Int a, Array Int a) -> (Int,Int) -> (Int,Int) -> a search k (xa,ya) (lx,rx) (ly,ry) | lx == rx = ya ! (k+ly) | ly == ry = xa ! (k+lx) | otherwise = case (xa ! mx < ya ! my) of (True) -> smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) (False) -> smallest2h k (ya,xa) ((ly,my,ry),(lx,mx,rx)) where mx = (lx+rx) `div` 2 my = (ly+ry) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array and ya the second array by their middle elements. smallest2h :: (Ord a) => Int -> (Array Int a, Array Int a) -> ((Int,Int,Int),(Int,Int,Int)) -> a smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) = case (k<=mx-lx+my-ly) of (True) -> search k (xa,ya) (lx,rx) (ly,my) (False) -> search (k-(mx-lx)-1) (xa,ya) (mx+1,rx) (ly,ry) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- Works on 3 finite ordered disjoint sets represented as sorted arrays. smallest3 :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> a smallest3 k (xa,ya,za) = -- On each recursive call the order of the arrays can switch. search3 k (xa,ya,za) (0,bx+1) (0,by+1) (0,bz+1) where (0,bx) = bounds xa (0,by) = bounds ya (0,bz) = bounds za -- Removed some of the "indexitis" at the cost of calling another function. search3 :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> (Int,Int) -> (Int,Int) -> (Int,Int) -> a search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,rz) | lx == rx && ly == ry = za ! (k+lz) | ly == ry && lz == rz = xa ! (k+lx) | lx == rx && lz == rz = ya ! (k+ly) | lx == rx = search k (ya,za) (ly,ry) (lz,rz) | ly == ry = search k (xa,za) (lx,rx) (lz,rz) | lz == rz = search k (xa,ya) (lx,rx) (ly,ry) | otherwise = case (xa ! mx < ya ! my, xa ! mx < za ! mz, ya ! my < za ! mz) of (True, True, True) -> smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) -- a<b<c (True, True, False) -> smallest3h k (xa,za,ya) ((lx,mx,rx),(lz,mz,rz),(ly,my,ry)) -- a<c<b (False, True, True) -> smallest3h k (ya,xa,za) ((ly,my,ry),(lx,mx,rx),(lz,mz,rz)) -- b<a<c (False, False, True) -> smallest3h k (ya,za,xa) ((ly,my,ry),(lz,mz,rz),(lx,mx,rx)) -- b<c<a (True, False, False) -> smallest3h k (za,xa,ya) ((lz,mz,rz),(lx,mx,rx),(ly,my,ry)) -- c<a<b (False, False, False) -> smallest3h k (za,ya,xa) ((lz,mz,rz),(ly,my,ry),(lx,mx,rx)) -- c<b<a where mx = (lx+rx) `div` 2 my = (ly+ry) `div` 2 mz = (lz+rz) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array, ya the second array, and za the third array by their middle elements. smallest3h :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> ((Int,Int,Int),(Int,Int,Int),(Int,Int,Int)) -> a smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) = case (k<=mx-lx+my-ly+mz-lz) of (True) -> search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,mz) (False) -> search3 (k-(mx-lx)-1) (xa,ya,za) (mx+1,rx) (ly,ry) (lz,rz) -- -- Regards, KC

1 0

"In several chapters there is a penetrating conceptual analysis of the matter at hand, on which a superstructure of code is erected."
by KC 20 May '11

20 May '11

Interesting comment on the book "The Fun of Programming" in JOOP. "In several chapters there is a penetrating conceptual analysis of the matter at hand, on which a superstructure of code is erected." -- -- Regards, KC

1 0

Is there a place where we can have a discussion on the merits of various GUI's & various graphics? And then vote?
by KC 20 May '11

20 May '11

:) -- -- Regards, KC

1 1

question about Yesod
by Michael Litchard 20 May '11

20 May '11

I admire what's been done with Yesod, especially in the example given by the Haskellers website. It's time I start making design decisions for my own website project, and I thought it would be a great idea to just steal from Haskellers liberally. My initial approach was to just gut Haskellers until everything I don't need is gone. This isn't working out as I had hoped. If it's not a huge pain in the butt, could someone put an example on github that does the following: I'm looking for the look of Haskellers. The tabs, and navbars is fine. The little bar that tracks what part of the site you are on would be bonus. Thanks for any help on this. Michael Litchard

2 1

Class and Instance Question
by Adam C. Emerson 20 May '11

20 May '11

Good morning, As my first "real" toy project (something trivial but with some pretense of usefulness at least to me) in Haskell, I had been trying to write an XDR encoder/decoder based on top of Data.Binary. As such, I have a typeclass: class Encodable t where -- | Encode a value in the Put monad. put :: t -> Put -- | Decode a value in the Get monad get :: Get t And I have various instances, all of which seem to work, except for two. My thought was to treat a list of Chars as a string and a list of "encodable" types as a counted array. Thus, I tried: instance Encodable [Char] where put s = put $ runPut (putUTF8str s) get = do bs <- get return (runGet getUTF8str bs) and instance (Encodable e) => Encodable [e] where put l = if (length l) > xdrmaxlen then fail "Length of data exceeds XDR maximum for arrays." else (put (length l) >> putFixed (length l) l) get = do n <- get getFixed n This failed, and the compiler suggested I try adding: {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE OverlappingInstances #-} But even with these two statements, I get: *Data.XDR.Encodable> encode [1, 2, 3] <interactive>:1:0: Overlapping instances for Encodable [t] arising from a use of `encode' at <interactive>:1:0-15 Matching instances: instance [overlap ok] (Encodable e) => Encodable [e] -- Defined at /home/azure/programming/xdr/src/Data/XDR/Encodable.hs:226:9-38 instance [overlap ok] Encodable [Char] -- Defined at /home/azure/programming/xdr/src/Data/XDR/Encodable.hs:160:9-24 (The choice depends on the instantiation of `t' To pick the first instance above, use -XIncoherentInstances when compiling the other instance declarations) In the expression: encode [1, 2, 3] So, the question I have, more than wondering how to get this to work (I suspect I shouldn't even be doing this, and instead I should newtype XDRInt and XDRString and so on), is why the two instances overlap. I have no instance for Char, so the first instance should apply to lists of Char (which isn't Encodable.) And the second should apply to lists of Encodable things (which Char isn't.) Is there a fairly comprehensible source I should read to understand typeclasses and instances better? (I've read my way through Real World Haskell, the Wikibook, and A Gentle Introduction, though it's possible they covered this and I just missed it.) Thank you.

4 3

Yesod question - ajax.lhs
by Michael Litchard 20 May '11

20 May '11

I'm using yesod 0.8.1 I'm playing around with yesod examples 0.8.0.1 and I noticed a few things that send up some red flags first thing, when I try to run ajax.lhs from the top level directory src/ajax.lhs:6:3: Warning: In the use of `string' (imported from Yesod, but defined in Text.Blaze.Internal): Deprecated: "Use Blaze.Html.toHtml" src/ajax.lhs:37:18: Warning: Deprecated syntax: quasiquotes no longer need a dollar sign: $parseRoutes src/ajax.lhs:52:21: Warning: Deprecated syntax: quasiquotes no longer need a dollar sign: $hamlet src/ajax.lhs:93:17: Warning: Deprecated syntax: quasiquotes no longer need a dollar sign: $hamlet This is suggesting to me the example code hasn't caught up to the changes in yesod, which can cause confusion for n00bs like me. I'm trying to learn how to use jQuery via yesod, and when I see the html generated from the current ajax.lhs this is what comes up <!DOCTYPE html><html><head><title>Page 1</title><link rel="stylesheet" href="/static/style%2Ecss?YaQxW21D"><script src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script><script src="/static/script%2Ejs?NWBIzSLG"></script></head><body><ul id="navbar"><li><a href="/page/page%2D1">Page 1</a></li><li><a href="/page/page%2D2">Page 2</a></li><li><a href="/page/page%2D3">Page 3</a></li></ul><div id="content"><h1>Page 1</h1><article>My first page</article></div></body></html> I want to draw attention to <script src="/static/script%2Ejs?NWBIzSLG"> and things like this. This is the other red flag that the example code hasn't caught up to the current state of Yesod. Am I interpreting the problem correctly? Here is what the latest example of ajax.lhs looks like. Could someone tell me what needs to change to prevent the above problems from happening? > {-# LANGUAGE TypeFamilies, QuasiQuotes, TemplateHaskell, MultiParamTypeClasses, OverloadedStrings #-} > import Yesod > import Yesod.Helpers.Static > import Data.Monoid (mempty) Like the blog example, we'll define some data first. > data Page = Page > { pageName :: String > , pageSlug :: String > , pageContent :: String > } > loadPages :: IO [Page] > loadPages = return > [ Page "Page 1" "page-1" "My first page" > , Page "Page 2" "page-2" "My second page" > , Page "Page 3" "page-3" "My third page" > ] > data Ajax = Ajax > { ajaxPages :: [Page] > , ajaxStatic :: Static > } > type Handler = GHandler Ajax Ajax > staticFiles "static/yesod/ajax" > mkYesod "Ajax" [$parseRoutes| > / HomeR GET > /page/#String PageR GET > /static StaticR Static ajaxStatic > |] > instance Yesod Ajax where > approot _ = "" > defaultLayout widget = do > Ajax pages _ <- getYesod > content <- widgetToPageContent widget > hamletToRepHtml [$hamlet| > \<!DOCTYPE html> > > <html> > <head> > <title>#{pageTitle content} > <link rel="stylesheet" href="@{StaticR style_css}"> > <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"> > <script src="@{StaticR script_js}"> > \^{pageHead content} > <body> > <ul id="navbar"> > $forall page <- pages > <li> > <a href="@{PageR (pageSlug page)}">#{pageName page} > <div id="content"> > \^{pageBody content} > |] > getHomeR :: Handler () > getHomeR = do > Ajax pages _ <- getYesod > let first = head pages > redirect RedirectTemporary $ PageR $ pageSlug first > getPageR :: String -> Handler RepHtmlJson > getPageR slug = do > Ajax pages _ <- getYesod > case filter (\e -> pageSlug e == slug) pages of > [] -> notFound > page:_ -> defaultLayoutJson (do > setTitle $ string $ pageName page > addHamlet $ html page > ) (json page) > where > html page = [$hamlet| > <h1>#{pageName page} > <article>#{pageContent page} > |] > json page = jsonMap > [ ("name", jsonScalar $ pageName page) > , ("content", jsonScalar $ pageContent page) > ] > main :: IO () > main = do > pages <- loadPages > let s = static "static/yesod/ajax" > warpDebug 3000 $ Ajax pages s

2 3

List operations
by jianqiuchi＠gmail.com 19 May '11

19 May '11

Hi, I have a question about the cost of list comprehension and map function. For example, I have a list of Double and I want to do lots of calculation on it. There are two ways to do that: 1. [x ** 3 | x <- list] 2. map (flip (**) 3) list I am wondering if the cost of using them could be very different and why. Thanks.

6 10

Re: [Haskell-beginners] [Haskell-cafe] For Euler 25; What is the first term in the Fibonacci sequence to contain 1000 digits?; the following seems to work.
by KC 19 May '11

19 May '11

Project Euler wants the term number not the actual Fibonacci number. I wonder what the compiled timings would be. :) On Thu, May 19, 2011 at 11:34 AM, Sebastian Fischer <fischer(a)nii.ac.jp> wrote: > > On Thu, May 19, 2011 at 7:29 PM, KC <kc1956(a)gmail.com> wrote: >> >> For Euler 25; What is the first term in the Fibonacci sequence to >> contain 1000 digits?; the following seems to work. >> >> >> -- For number of digits being 5 or more. >> fibNdigits :: Int -> Int >> fibNdigits nDigits = floor (((fromIntegral nDigits) - 1.0) / (logBase >> 10 phi)) + 2 >> where >> sq5 = sqrt 5 :: Double >> phi = (1 + sq5) / 2 > > > (length . show) is fast enough for me. The following gives the answer in a > fraction of a second. > # cabal install fibonacci > # ghci > ghci> import Data.Numbers.Fibonacci > ghci> head . filter ((==1000) . length . show) $ map fib [0..] > 1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816 > -- -- Regards, KC

2 1

Worth repeating Daniel's comment: Don't benchmark in ghci, use compiled code.
by KC 19 May '11

19 May '11

Worth repeating Daniel's comment. Don't benchmark in ghci, use compiled code. -- -- Regards, KC

1 0

For Euler 25; What is the first term in the Fibonacci sequence to contain 1000 digits?; the following seems to work.
by KC 19 May '11

19 May '11

For Euler 25; What is the first term in the Fibonacci sequence to contain 1000 digits?; the following seems to work. -- For number of digits being 5 or more. fibNdigits :: Int -> Int fibNdigits nDigits = floor (((fromIntegral nDigits) - 1.0) / (logBase 10 phi)) + 2 where sq5 = sqrt 5 :: Double phi = (1 + sq5) / 2 -- -- Regards, KC

1 0