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: code critique (Gary Klindt)
2. Re: lazyness and tail recursion (Will Ness)
3. Re: code critique (Jeff Lasslett)
4. Re: code critique (Arlen Cuss)
5. Re: code critique (Alexander Batischev)
6. Re: code critique (Arlen Cuss)
7. Re: code critique (Alexander Batischev)
8. Code-review of "toy SQL" parser using Parsec (Andy Elvey)
----------------------------------------------------------------------
Message: 1
Date: Tue, 26 Jul 2011 23:33:27 +0200
From: Gary Klindt <[email protected]>
Subject: Re: [Haskell-beginners] code critique
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hey all!
I compared the different methods proposed with my eyes and the profiler.
sumCheck1 _ [] _ = Nothing
sumCheck1 total (x:xs) ys = if total' == Nothing
then sumCheck total xs ys
else return (x,(ys!!(fromJust total')))
where total' = elemIndex (total-x) ys
sumCheck2 total (x:xs) ys =
let diff = total - x
in if elem diff ys
then Just (x,diff)
else sumCheck total xs ys
sumCheck3 i as bs = not $ null [(x,y) | x <- as, y <- bs, x+y==i ]
It is fascinating how small the code can be with list comprehensions.
Unfortunately the third solution needs much more memory during run time
than the other two.
Increasing the list size leads to heavy growth of memory allocation.
Probably the evaluation of the cross product in sumCheck3 is not very
lazy (but why not?).
The first two solutions scale very well.
Cheers
On 07/26/2011 08:31 AM, aditya siram wrote:
> List comprehension seems like the easiest way to do it.
>
> First here's how to get the cross product of two lists, I'll be using
> this below:
> cp as bs = [(x,y) | x<- as, y<- bs ]
> -- cp [1,2,3] [4,5,6] =
> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
>
> Then constrain the cross product to tuples where the sum is the given number:
> sums i as bs = [(x,y) | x<- as, y<- bs, x + y == i]
> -- sums 4 [1,2,3] [1,2,3] == [(1,3),(2,2),(3,1)]
>
> Then check that the list of constrained sums is not empty:
> sumCheck i as bs = not (null (sums i as bs))
>
> -deech
>
> On Mon, Jul 25, 2011 at 10:52 PM, Bryce Verdier<[email protected]>
> wrote:
>> Hi all,
>> I'm new to haskell, and I'm trying to get better with it. Recently I
>> completed one of the challenges from Programming Praxis and I was wondering
>> if people would be willing to spend some time and tell me how I could
>> improve my code.
>> Thanks in advance,
>> Bryce
>> Here is a link to the programming praxis:
>> http://programmingpraxis.com/2011/07/19/sum-of-two-integers/
>> And here is my code:
>> import Data.List
>> import Data.Maybe
>> sumCheck :: Int -> [Int] -> [Int] -> Maybe (Int, Int)
>> sumCheck _ [] _ = Nothing
>> sumCheck total (x:xs) ys = if total' == Nothing
>> then sumCheck total xs ys
>> else return (x, (ys !! ( fromJust total')))
>> where total' = (total - x) `elemIndex` ys
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 2
Date: Tue, 26 Jul 2011 22:38:03 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: Re: [Haskell-beginners] lazyness and tail recursion
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Ovidiu Deac <ovidiudeac <at> gmail.com> writes:
>
> I've read the paragraph below from Real World Haskell
>
(http://book.realworldhaskell.org/read/efficient-file-processing-regular-expressions-and-file-name-matching.html
> section "An important aside: writing lazy functions")
>
> I can get a feeling why lazyness compensates for the lack of tail
> recursion but I don't really understand why it would work in general.
>
> My understanding is that that a function which returns a list with
> non-tail recursion would only work this way with certain usage
> patterns. In this case the caller of the funtion will have to use the
> string in a stream-like fashion.
The concept of tail recursion modulo cons is similar. Wikipedia has an article.
Basically it's about keeping one execution frame above the tail-recursive one.
Lazily accessing a list from the top is a lot like adding elements to it one by
one at the bottom. Prefixing a recursive call with an operation of fixed number
of operations is OK, because they will get consumed and the recursive case
called, in a fixed number of steps - the instance between current point and next
recursive invocation point won't grow, only get increased at times by a set
amount and then get consumed.
The problem with non-tail recursion in lazy setting is that the distance grows
between the current point and the next invocation, and so the amount of "what to
do next?" information grows all the time. In imperative setting it gets flipped
into "what to do after the invocation" but it still grows. In tail-recursion
(even modulo cons, or (++) with fixed prefix) it's bounded, finite, constant.
Looking at Scheme example code in WP "continuation-passing style" article might
help. There we see as in translations of tail-recursive functions the
constructed continuation does not grow in unlimited fashion, instead only maybe
getting prefixed by a fixed amount of operations at times.
Does it make any sense? :)
------------------------------
Message: 3
Date: Wed, 27 Jul 2011 09:47:14 +1000
From: Jeff Lasslett <[email protected]>
Subject: Re: [Haskell-beginners] code critique
To: [email protected]
Message-ID:
<cak6+hbysyrfuokrjjcwggcqxb4bgf5am_xmcau1oer8ccpw...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Also, if I understand correctly, solutions 1 & 2 will only produce one
pair, whereas solution 3 (based on list comprehensions) will produce
all pairs that sum to the total.
On 27 July 2011 07:33, Gary Klindt <[email protected]> wrote:
> Hey all!
>
> I compared the different methods proposed with my eyes and the profiler.
>
> sumCheck1 _ ? ? [] ? ? _ ?= Nothing
> sumCheck1 total (x:xs) ys = if total' == Nothing
> ? ? ? ? ? ? ? ? ? ? ? ? ? then sumCheck total xs ys
> ? ? ? ? ? ? ? ? ? ? ? ? ? else return (x,(ys!!(fromJust total')))
> ? ? ? ? ? ? ? ? ? ? ? ? ? where total' = elemIndex (total-x) ys
>
> sumCheck2 total (x:xs) ys =
> ? ?let diff = total - x
> ? ?in if elem diff ys
> ? ? ? then Just (x,diff)
> ? ? ? else sumCheck total xs ys
>
> sumCheck3 i as bs = not $ null [(x,y) | x <- as, y <- bs, x+y==i ]
>
> It is fascinating how small the code can be with list comprehensions.
> Unfortunately the third solution needs much more memory during run time than
> the other two.
> Increasing the list size leads to heavy growth of memory allocation.
> Probably the evaluation of the cross product in sumCheck3 is not very lazy
> (but why not?).
> The first two solutions scale very well.
>
> Cheers
>
>
>
> On 07/26/2011 08:31 AM, aditya siram wrote:
>>
>> List comprehension seems like the easiest way to do it.
>>
>> First here's how to get the cross product of two lists, I'll be using
>> this below:
>> cp as bs = [(x,y) | x<- as, y<- bs ]
>> -- cp [1,2,3] [4,5,6] =
>> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
>>
>> Then constrain the cross product to tuples where the sum is the given
>> number:
>> sums i as bs = [(x,y) | x<- as, y<- bs, x + y == i]
>> -- sums 4 [1,2,3] [1,2,3] == [(1,3),(2,2),(3,1)]
>>
>> Then check that the list of constrained sums is not empty:
>> sumCheck i as bs = not (null (sums i as bs))
>>
>> -deech
>>
>> On Mon, Jul 25, 2011 at 10:52 PM, Bryce Verdier<[email protected]>
>> ?wrote:
>>>
>>> Hi all,
>>> I'm new to haskell, and I'm trying to get better with it. Recently I
>>> completed one of the challenges from Programming Praxis and I was
>>> wondering
>>> if people would be willing to spend some time and tell me how I could
>>> improve my code.
>>> Thanks in advance,
>>> Bryce
>>> Here is a link to the programming praxis:
>>> http://programmingpraxis.com/2011/07/19/sum-of-two-integers/
>>> And here is my code:
>>> import Data.List
>>> import Data.Maybe
>>> sumCheck :: Int -> ?[Int] -> ?[Int] -> ?Maybe (Int, Int)
>>> sumCheck _ [] _ = Nothing
>>> sumCheck total (x:xs) ys = if total' == Nothing
>>> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? then sumCheck total xs ys
>>> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? else return (x, (ys !! ( fromJust
>>> total')))
>>> ? ? ? ? ? ? ? ? ? ? ? ? ? ?where total' = (total - x) `elemIndex` ys
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 4
Date: Wed, 27 Jul 2011 10:31:15 +1000
From: Arlen Cuss <[email protected]>
Subject: Re: [Haskell-beginners] code critique
To: Jeff Lasslett <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
27/07/2011 9:47 AM, Jeff Lasslett kirjutas:
> Also, if I understand correctly, solutions 1 & 2 will only produce one
> pair, whereas solution 3 (based on list comprehensions) will produce
> all pairs that sum to the total.
Correct, though it discards them in the end and only returns a Bool.
That it does collect all the answers (before discarding) is probably why
it has such a memory hit.
> sumCheck1 _ [] _ = Nothing
> sumCheck1 total (x:xs) ys = if total' == Nothing
> then sumCheck total xs ys
> else return (x,(ys!!(fromJust total')))
> where total' = elemIndex (total-x) ys
>
> sumCheck2 total (x:xs) ys =
> let diff = total - x
> in if elem diff ys
> then Just (x,diff)
> else sumCheck total xs ys
>
> sumCheck3 i as bs = not $ null [(x,y) | x <- as, y <- bs, x+y==i ]
------------------------------
Message: 5
Date: Wed, 27 Jul 2011 03:34:23 +0300
From: Alexander Batischev <[email protected]>
Subject: Re: [Haskell-beginners] code critique
To: [email protected]
Message-ID: <20110727003423.GA18534@speedy>
Content-Type: text/plain; charset="us-ascii"
Hi!
On Wed, Jul 27, 2011 at 09:47:14AM +1000, Jeff Lasslett wrote:
> Also, if I understand correctly, solutions 1 & 2 will only produce one
> pair, whereas solution 3 (based on list comprehensions) will produce
> all pairs that sum to the total.
>
> On 27 July 2011 07:33, Gary Klindt <[email protected]> wrote:
> > sumCheck3 i as bs = not $ null [(x,y) | x <- as, y <- bs, x+y==i ]
Maybe I misunderstood you, but you aren't quite right. In third
solution, *list comprehension* will produce all the pairs. But you're
applying 'null' to it, and since everything in Haskell is lazy by
default, only *one* pair will be produced.
Just for your information: that's why it's always advised to use 'null'
to check if list is empty. Newbies often try to do that in more obvious
way:
length list == 0
but that have very nasty consequence: to calculate length of the list,
you should compute the value of each element. If you use null, only
first (if any) element gets computed, and then null immediately returns.
Ah, yes, one more note: first two solutions return pair that satisfies
your task, while third solution will only return some Bool value
indicating if such pair exists.
--
Regards,
Alexander Batischev
1024D/69093C81
F870 A381 B5F5 D2A1 1B35 4D63 A1A7 1C77 6909 3C81
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20110727/a94f3366/attachment-0001.pgp>
------------------------------
Message: 6
Date: Wed, 27 Jul 2011 11:19:03 +1000
From: Arlen Cuss <[email protected]>
Subject: Re: [Haskell-beginners] code critique
To: Alexander Batischev <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
> Maybe I misunderstood you, but you aren't quite right. In third
> solution, *list comprehension* will produce all the pairs. But
> you're applying 'null' to it, and since everything in Haskell is lazy
> by default, only *one* pair will be produced.
Good point! Lovely way to show this is with 'trace':
> :m +Debug.Trace null [x | x <- [trace "a" 5, trace "b" 10, trace "c"
> 15]]
False
> null [x | x <- [trace "a" 5, trace "b" 10, trace "c" 15], x > 0]
a
False
> null [x | x <- [trace "a" 5, trace "b" 10, trace "c" 15], x > 5]
a
b
False
> null [x | x <- [trace "a" 5, trace "b" 10, trace "c" 15], x > 10]
a
b
c
False
>
(Of course, this is less beautifully illustrated with 'length', because
it doesn't actually evaluate the values ...:
> length [trace "a" 5, trace "b" 10, trace "c" 15] == 0
False
>
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.17 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iQIcBAEBAgAGBQJOL2eHAAoJEDiWqExGnQ/QIyMQAK5UhXziU8ctse3K2aUrwrbm
BrQd4ec7i3nCqM0ykkwV9jAAZdHKL3Hu1gWPzH7kBOmcSBcfE3/0woZOna10cSry
jovsAHt5eiE/ujqGWkWeidVSu3wcNcoMXm0ZjdTG5FPx9O+YXvmCRzaxUp0lYZzO
w3tRy4tQPLogcfR72HLlk6IBdG/8d04shQ8lTgRmbRKALI/VN2N8+qqYSsZySiF9
SmE2yQIG3pwSm6QNCCeCGudoz2qjN7SIM4443pjOMJODda1dLpliuC0eo9q+4YSW
ZOH8oJFGembav2C6epYw8qLkSB0bvJltohspZK5GifeSUEWZT36WAbqF0NOAOn6D
du0JW/bEazLiph2NNC2qzqjWDAnoYmY1Nqx3tob2UDMslf8h2H8vMvTiUKKU2tED
h33HgLWfW0l+MPaAvIdTDNscm1/dExleyrtsc6PMA5If650wdjITzHFqQ+9fCYD8
Qbd475cOL5ZkbQjGRlIzgq5goH9JUOv5wqIjz9LOKd1q6KGLq5UN3OTEyjkDt1vo
zGtMjQqgha/M3sznXVUTkBc12gFotVYuUmUCOQFEafjxhtN46JR0fNHJjOFzpqb6
Jkqd75GvOHJCfNUkMc42ZDEWXDzBO38f3Vgouf6VRK+/yDqqOSXyK+/SspQwLuFk
Ph9fI7dGT178rNQpdU3A
=gZUe
-----END PGP SIGNATURE-----
------------------------------
Message: 7
Date: Wed, 27 Jul 2011 04:39:47 +0300
From: Alexander Batischev <[email protected]>
Subject: Re: [Haskell-beginners] code critique
To: [email protected]
Message-ID: <20110727013947.GB1757@speedy>
Content-Type: text/plain; charset="us-ascii"
Hi!
On Wed, Jul 27, 2011 at 11:19:03AM +1000, Arlen Cuss wrote:
> (Of course, this is less beautifully illustrated with 'length', because
> it doesn't actually evaluate the values ...:
>
> > length [trace "a" 5, trace "b" 10, trace "c" 15] == 0
> False
> >
Oh, excuse me - yes, 'length' really doesn't evaluate the values. But
still, it *builds* the list (that may be very large or even infinite),
thus slowing or even hanging your program.
--
Regards,
Alexander Batischev
1024D/69093C81
F870 A381 B5F5 D2A1 1B35 4D63 A1A7 1C77 6909 3C81
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20110727/c753c8fe/attachment-0001.pgp>
------------------------------
Message: 8
Date: Wed, 27 Jul 2011 15:02:29 +1200
From: Andy Elvey <[email protected]>
Subject: [Haskell-beginners] Code-review of "toy SQL" parser using
Parsec
To: Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
Hi all -
I'm poking around with Parsec and looking at getting this "toy SQL"
parser up and running.
So, I'm keen to get feedback on whether I'm on the right track (or off
on a siding to nowhere..... ;) )
This is my first Parsec grammar, so I hope you'll be gentle...... :)
( Note - I've put the whereStmt in parens as I want that to be an
optional statement. I'm not sure how
to denote that in Parsec. )
Many thanks in advance -
** Start of code **
-- toysql.hs
-- This code is aimed at parsing phrases like the
-- following -
-- select * from mytable where city = "Sydney";
-- select foo, bar from mytable where var1 > 10;
-- select baz from mytable;
-- This code is released to the public domain.
-- "Share and enjoy....." ;)
module Main where
import Text.ParserCombinators.Parsec
sqlStmt = do{ createStmt
; selectStmt
; fromStmt
; (whereStmt)
; semicolon
}
createStmt = do{ CREATE
; tablename
; AS
}
tablename = identifier
selectStmt = do{ SELECT
; varStmt
}
varStmt = star <|> singlevar <|> varlist
star = '*'
singlevar = identifier
varlist = sepBy singlevar (char ',')
fromStmt = do{ FROM
; tableStmt
}
tableStmt = singleTablestmt <|> multiTablestmt
singleTablestmt = identifier
multiTablestmt = sepBy identifier (char ',')
whereStmt = do{ WHERE
; condStmt
}
condStmt = multiCondstmt <|> singleCondstmt
singleCondstmt = singleCondstmtnoparens <|> singleCondstmtwithparens
singleCondstmtnoparens = do{
; singlevar
; OP
; value
}
singleCondstmtwithparens = do(
; char '('
; singleCondstmtnoparens
; char ')'
multiCondstmt = sepBy singleCondstmt ( AND <|> OR )
OP = ( '=' <|> '<' <|> '>' <|> "<=" <|> ">=" <|> "!=" )
semicolon = char ';'
parseSQL :: String -> Either ParseError [[String]]
parseSQL input = parse sqlFile "(unknown)" input
** end of code **
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20110727/1d5dc200/attachment.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 37, Issue 60
*****************************************
