Send Beginners mailing list submissions to
beginners@haskell.org
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
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Thompson Exercise 9.13 (Daniel Fischer)
2. Having fun with yesod, and a few questions came up.
(Michael Litchard)
3. Re: Having fun with yesod, and a few questions came up.
(Michael Snoyman)
----------------------------------------------------------------------
Message: 1
Date: Thu, 15 Jul 2010 17:19:46 +0200
From: Daniel Fischer <daniel.is.fisc...@web.de>
Subject: Re: [Haskell-beginners] Thompson Exercise 9.13
To: dan portin <danpor...@gmail.com>
Cc: beginners@haskell.org
Message-ID: <201007151719.47047.daniel.is.fisc...@web.de>
Content-Type: text/plain; charset="utf-8"
On Thursday 15 July 2010 15:46:15, dan portin wrote:
> > [...] it needs to traverse the entire list before it can start
> > assembling the result.
> > To avoid that, so the result can be assembled from the start of the
> > list, you need to make the pattern match on the second argument lazy,
> >
> > f (x,y) ~(xs,ys) = (x:xs,y:ys)
> >
> > or
> >
> > f (x,y) p = (x : fst p, y : snd p)
> >
> > Now
> >
> > f (x,y) (f (x1,y1) ([],[]))
> > ~> let (xs,ys) = f (x1,y1) ([],[]) in (x:xs, y:ys)
>
> This makes sense. I didn't realize Haskell was doing this.
I said it was subtle :)
> Of course, that could be a downside to evaluating by
> hand on paper, where you often 'think lazily.' I assumed Haskell
> evaluated the expression in a similar way to
> your 'let ...' clause.
>
Pattern matching is strict (if you're matching against a refutable pattern;
matching a variable pattern or wildcard always succeeds, so no evaluation
is ever necessary then).
Another way to achieve the same is
f (x,y) p = let (xs,ys) = p in (x:xs, y:ys)
Patterns bound in a let-expression or where-clause have an implicit ~, so a
potential pattern-match failure is only reported when you're demanding a
bound value which isn't there:
Prelude> let foo x mb = let Just xs = mb in Just (x:xs)
Prelude> foo True Nothing
Just [True*** Exception: <interactive>:1:19-30: Irrefutable pattern failed
for pattern Data.Maybe.Just xs
> > > *last* :: [a] -> a
> > > last xs = head $ foldr f [] xs
> > > where f :: a -> [a] -> [a]
> > > f x [] = [x]
> > > f x ys = ys ++ [x]
> >
> > last xs = head (reverse xs), yes, it's correct, but not very pretty.
> > And not very efficient since it builds a left-associated nest of (++)
> > applications and needs to pattern match to decide which branch to
> > take.
> >
> > last (1:2:3:4:[])
> > ~> head $ foldr f [] (1:2:3:4:[])
> > ~> head $ f 1 (f 2 (f 3 (f 4 [])))
> > ~> head $ f 1 (f 2 (f 3 [4]))
> > ~> head $ f 1 (f 2 ([4] ++ [3]))
> > ~> head $ f 1 (([4] ++ [3]) ++ [2])
> > ~> head $ ((([4] ++ [3]) ++ [2]) ++ [1]
> >
> > a) in the second branch of f, you don't actually need to concatenate,
> >
> > f x [] = [x]
> > f _ ys = ys
> >
> > works too, but is faster.
> >
> > b) you can get much faster by delaying the pattern match,
> >
> > f x ys = (case ys of { [] -> x; y:_ -> y }) : []
>
> Yes, nesting each element inside (++) operators was an oversight on my
> part. Your solution (a) is much cleaner, since
>
> head $ foldr f [] (1:2:3:[])
> ~> head $ f 1 (f 2 (f 3 []))
> ~> head $ f 1 (f 2 (3:[]))
> ~> head $ f 1 (3:[])
> ~> head $ (3:[])
>
> I'm confused about (b), however. I was under the
> impression<http://www.haskell.org/tutorial/patterns.html>that the
> pattern match
>
> f P1 ... P1N = E1
> f P2 ... P2N = E2
>
> is *semantically* equivalent to
>
> f x1 ... xn = case (x1, ..., xn) of { P1 ... P1n -> E1; P2 ... P2n ->
> E2}.
>
> Of course, "semantically equivalent" doesn't mean "as efficient."
That's the one point.
However, that's not the point here. It was late and very hot, so I didn't
write it as clear as was desirable, the function in b) can also be written
as
f x ys = z : []
where
z = case ys of
[] -> x
y:_ -> y
I think that makes it more understandable, the point is that the
constructor (:) is applied on the RHS before we look whether ys matches []
or (_:_).
If we evaluate it for a short list:
head $ foldr f [] (1:2:3:[])
~> head $ f 1 (foldr f [] (2:3:[]))
~> head (z1 : [])
where z1 = case foldr f [] (2:3:[]) of { [] -> 1; y:_ -> y }
~> z1 where z1 = case foldr f [] (2:3:[]) of { [] -> 1; y:_ -> y }
~> case foldr f [] (2:3:[]) of { [] -> 1; y:_ -> y }
~> case f 2 (foldr f [] (3:[])) of { [] -> 1; y:_ -> y }
~> case z2 : [] of { [] -> 1; y:_ -> y }
where
z2 = case foldr f [] (3:[]) of { [] -> 2; w:_ -> w }
~> z2 where z2 = case foldr f [] (3:[]) of { [] -> 2; w:_ -> w }
~> case foldr f [] (3:[]) of { [] -> 2; w:_ -> w }
~> case f 3 (foldr f [] []) of { [] -> 2; w:_ -> w }
~> case z3 : [] of { [] -> 2; w:_ -> w }
where
z3 = case foldr f [] [] of { [] -> 3; v:_ -> v }
~> z3 where z3 = case foldr f [] [] of { [] -> 3; v:_ -> v }
~> case foldr f [] [] of { [] -> 3; v:_ -> v }
~> case [] of { [] -> 3; v:_ -> v }
~> 3
We never have deep nesting, we always have progress looking at no more than
two successive list elements and can let the start of the list be garbage
collected almost immediately.
Now with
g x [] = [x]
g _ ys = ys
we get
head $ foldr g [] (1:2:3:[])
~> head $ g 1 (foldr g [] (2:3:[]))
-- we don't know which branch to take for g 1 _, so we
-- must evaluate foldr g [] (2:3:[]) to see
~> head $ g 1 (g 2 (foldr g [] (3:[])))
-- we don't know which branch to take for g 2 _, so
~> head $ g 1 (g 2 (g 3 (foldr g [] [])))
-- we don't know which branch to take for g 3 _, so
~> head $ g 1 (g 2 (g 3 []))
~> head $ g 1 (g 2 [3])
~> head $ g 1 [3]
~> head $ [3]
~> 3
And you see that we get nested calls to g, the nesting depth is length list
and we hold on to the start of the list until we can finally apply head.
This doesn't require more reduction steps [both need O(length list) steps],
but it requires O(length list) space vs O(1) space for the f above, hence
this is much slower.
> I don't understand whether the move from matching against
> '_ ys' to y:_ is supposed to make the definition of f more efficient to
> compute, or whether the use of case expressions is
> supposed to.
>
What makes it more efficient is that we start constructing the result
before we investigate the arguments. Thus we can know which branch to take
before we've reached the end of the list.
> > > *init* :: [a] -> [a]
> > > init xs = tail $ foldr f [] xs
> > > where f :: a -> [a] -> [a]
> > > f x [] = [x]
> > > f x (y:xs) = y : x : xs
> >
> > Correct too, but again not very efficient since it has to find the
> > last element and bubble it to the front.
> >
> > Much faster:
> >
> > import Data.Maybe (fromMaybe)
> >
> > init' :: [a] -> [a]
> > init' = fromMaybe (error "init': empty list") . foldr f Nothing
> > where
> > f x mb = Just $ case mb of
> > Just xs -> x:xs
> > Nothing -> []
> >
> > By delaying the pattern match on the Maybe until after the constructor
> > is applied, we can start building the output with minimal delay (we
> > only need to look whether there's a next list element to decide
> > whether to cons it to the front or not).
>
> I'm not sure what you mean by "applying the constructor [Just],"
Similar to the above,
f x mb = Just zs
where
zs = case mb of
Just xs -> x:xs
Nothing -> []
By having the result Just something before we inspect the arguments, we can
start building the result almost immediately, we only have to see whether
the second argument comes from a call to f (in other words, whether there's
at least one further element in the list) to know which branch to take.
If we pattern match first, we again build a nest of applications of f until
we reach the end of the list and can only then start to unwind the stack.
> or which function
> you are forcing to evaluate (after 'applying the constructor').
> Obviously, I need to
> learn more about Haskell's monads and type constructors.
>
Nothing to do with monads, it's all about laziness and pattern matching.
As a general rule, in
foldr fun z xs
you want fun to be as lazy as possible in its second argument, i.e. do
everything you can do before even looking at it.
If you can even do something before looking at fun's first argument, all
the better.
> > > (2) Is there a way to eliminate the
> > > post-processing of the lists (i.e., *head* in *last* and *tail* in
> > > *init*)?
> >
> > Not in a clean way.
> >
> > Let us consider last first.
> >
> > Suppose we had
> >
> > last xs = foldr f z xs
> >
> > without post-processing.
> > Since foldr f z [] = z and last [] = error "Prelude.last: empty list",
> > we must have z = error "...".
> > Now last (... x:[]) = x and
> > foldr f z (... x:[]) = ... (f x z)
> >
> > So f x y = y if y is not error "..." and f x (error "...") = x, that
> > means f would have to find out whether its second argument is a
> > specific error and return its first argument in that case, otherwise
> > its second argument. It's possible to do that, but very unclean.
>
> That's helpful. I was trying to *name* a list at a particular stage of
> construction, and it
> failed for just this reason.
------------------------------
Message: 2
Date: Thu, 15 Jul 2010 08:57:04 -0700
From: Michael Litchard <mich...@schmong.org>
Subject: [Haskell-beginners] Having fun with yesod, and a few
questions came up.
To: beginners@haskell.org
Message-ID:
<aanlktil4kzgh2dfw2k-sbcxscdimtnzgy9-3l6dac...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
I'm playing with yesod http://docs.yesodweb.com/yesod/, and I have a
few questions:
Here's an excerpt from yesod/tutorial/i18n.lhs
**NOTE: This tutorial requires the development version of Yesod
(version 0.4.0). The [tutorial main page]($root/yesod/tutorial/) has
instructions on setting up your environment.**
Where is $root?
I thought it was where yesod-examples-0.4.0 was installed. But if this
is the case, I'm not finding these instructions. This makes me think I
am confused about the directory $root represents.
I was playing around with the code and made some changes. Here is the
line in question, with the complete code below for context.
> instance Yesod I18N where
> approot _ = ""
This does what I expect it to do, it runs the program when I open up
http://my.blog.server/
however, I wanted to see what would happen if I played around with it
a little bit. I want the same program to run when I point my browser
to http://my.blog.server/blog
so I made this change
> approot _ = "/blog"
but now when I point my browser to http://my.blog.server/blog it gets
re-written to http:/my.blog.server/blog/blog
and then this error message
Not Found
/blog/blog
Not sure what is going on here, could someone enlighten me?
---
title: Multi-lingual -- Tutorials -- Yesod
---
**NOTE: This tutorial requires the development version of Yesod
(version 0.4.0). The [tutorial main page]($root/yesod/tutorial/) has
instructions on setting up your environment.**
> {-# LANGUAGE QuasiQuotes #-}
> {-# LANGUAGE TemplateHaskell #-}
> {-# LANGUAGE TypeFamilies #-}
> import Yesod
> import Data.Monoid (mempty)
> data I18N = I18N
> mkYesod "I18N" [$parseRoutes|
> / HomepageR GET
> /set/#String SetLangR GET
> |]
> instance Yesod I18N where
> approot _ = "/blog"
> getHomepageR :: Handler I18N RepHtml
> getHomepageR = do
> ls <- languages
> let hello = chooseHello ls
> let choices =
> [ ("en", "English")
> , ("es", "Spanish")
> , ("he", "Hebrew")
> ]
> applyLayout "I18N Homepage" mempty [$hamlet|
> %h1 $hello$
> %p In other languages:
> %ul
> $forall choices choice
> %li
> %a!hr...@setlangr.fst.choice@ $snd.choice$
> |]
> chooseHello :: [String] -> String
> chooseHello [] = "Hello"
> chooseHello ("he":_) = "ש×~\×~U×~]"
> chooseHello ("es":_) = "Hola"
> chooseHello (_:rest) = chooseHello rest
> getSetLangR :: String -> Handler I18N ()
> getSetLangR lang = do
> setLanguage lang
> redirect RedirectTemporary HomepageR
> main :: IO ()
> main = basicHandler 3000 I18N
------------------------------
Message: 3
Date: Thu, 15 Jul 2010 19:33:17 +0300
From: Michael Snoyman <mich...@snoyman.com>
Subject: Re: [Haskell-beginners] Having fun with yesod, and a few
questions came up.
To: Michael Litchard <mich...@schmong.org>
Cc: beginners@haskell.org
Message-ID:
<aanlktikc9pn-fcitzjkbzlgrcuki85hcp6631feio...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Thu, Jul 15, 2010 at 6:57 PM, Michael Litchard <mich...@schmong.org>wrote:
> I'm playing with yesod http://docs.yesodweb.com/yesod/, and I have a
> few questions:
>
> Here's an excerpt from yesod/tutorial/i18n.lhs
>
> **NOTE: This tutorial requires the development version of Yesod
> (version 0.4.0). The [tutorial main page]($root/yesod/tutorial/) has
> instructions on setting up your environment.**
>
> Where is $root?
> I thought it was where yesod-examples-0.4.0 was installed. But if this
> is the case, I'm not finding these instructions. This makes me think I
> am confused about the directory $root represents.
>
> Sorry about the $root stuff, it's an artifact from the web site. I use the
same code base for the yesod-examples package and the tutorials on the site
to make sure everything compiles properly. In any event, the line in
question is out-of-date and needs to be removed: 0.4.0 has been officially
released, so you just need a cabal install yesod to get started.
I was playing around with the code and made some changes. Here is the
> line in question, with the complete code below for context.
>
> > instance Yesod I18N where
> > approot _ = ""
>
> This does what I expect it to do, it runs the program when I open up
> http://my.blog.server/
>
> however, I wanted to see what would happen if I played around with it
> a little bit. I want the same program to run when I point my browser
> to http://my.blog.server/blog
>
> so I made this change
> > approot _ = "/blog"
>
> but now when I point my browser to http://my.blog.server/blog it gets
> re-written to http:/my.blog.server/blog/blog
> and then this error message
> Not Found
> /blog/blog
>
> Not sure what is going on here, could someone enlighten me?
>
>
> The approot function is used for *rendering* routes. This has no affect on
where Yesod *listens* to requests. For example, you could put approot _ = "
http://haskell.org";, but you wouldn't be able to respond to requests for
that domain. Nonetheless, URLs generated by Yesod would then point to
haskell.org.
Basically, the only time to get fancy with approot is when you're doing URL
rewriting for (Fast)CGI hosted applications. When you use a standalone
server, you'll always* be serving from the root of the domain, and so the
value of approot should just be that domain name.
* Of course, there's always exceptions.
You might look at the documentation[1] where it explains when it's
permissible to use an empty string for the value of approot.
Michael
[1] http://docs.yesodweb.com/haddock/yesod/Yesod-Yesod.html#v%3Aapproot
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100715/4998ddc1/attachment-0001.html
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 25, Issue 36
*****************************************
