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: maximum: stack overflow? (Roland Zumkeller)
2. Re: maximum: stack overflow? (Alexander Dunlap)
3. Re: maximum: stack overflow? (Roland Zumkeller)
4. Re: maximum: stack overflow? (Chadda? Fouch?)
5. Re: Integer factorization (Heinrich Apfelmus)
6. Re: Re: Integer factorization (Sergey V. Mikhanov)
7. Longest common subsequence (Leslie P. Polzer)
8. Re: Re: Integer factorization (Colin Paul Adams)
----------------------------------------------------------------------
Message: 1
Date: Fri, 13 Mar 2009 00:33:18 -0400
From: Roland Zumkeller <[email protected]>
Subject: Re: [Haskell-beginners] maximum: stack overflow?
To: Patrick LeBoutillier <[email protected]>
Cc: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi Patrick,
On Thu, Mar 12, 2009 at 10:35 PM, Patrick LeBoutillier
<[email protected]> wrote:
> *Main> maximum [1..1000000]
> *** Exception: stack overflow
>
> It seems to me like maximum should just be going through the list one
> by one and keeping track on the
> largest element seen do far. Why does in need to keep the entire list
> around (I presume), causing the stack overflow?
This is due to non-strict evaluation. The Prelude defines
maximum xs = foldl1 max xs
for non-empty xs and
foldl1 f (x:xs) = foldl f x xs.
Instead of just maintaining an integer in its first argument, foldl
constructs a chain of thunks, i.e. expressions awaiting evaluation.
You can use the strict version of foldl1 (called foldl1') to avoid
this problem:
*Main> import Data.List
*Main Data.List> foldl1' max [1..1000000]
1000000
A more detailed explanation can be found here:
http://www.haskell.org/haskellwiki/Stack_overflow
Why is maximum not defined in terms of foldl1'? Probably because
situations in which non-strictness is beneficial are thought to be
more common. Also, the two are not equivalent:
*Main Data.List> foldl1 (flip (||)) [undefined,False,True]
True
*Main Data.List> foldl1' (flip (||)) [undefined,False,True]
*** Exception: Prelude.undefined
Best,
Roland
--
http://roland.zumkeller.googlepages.com/
------------------------------
Message: 2
Date: Thu, 12 Mar 2009 21:43:07 -0700
From: Alexander Dunlap <[email protected]>
Subject: Re: [Haskell-beginners] maximum: stack overflow?
To: Roland Zumkeller <[email protected]>
Cc: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On Thu, Mar 12, 2009 at 9:33 PM, Roland Zumkeller
<[email protected]> wrote:
> Why is maximum not defined in terms of foldl1'? Probably because
> situations in which non-strictness is beneficial are thought to be
> more common.
How did this get established? Isn't maximum always (semantically)
strict anyway? I.e.
maximum [1,2,undefined] = undefined
Alex
------------------------------
Message: 3
Date: Fri, 13 Mar 2009 01:05:48 -0400
From: Roland Zumkeller <[email protected]>
Subject: Re: [Haskell-beginners] maximum: stack overflow?
To: Alexander Dunlap <[email protected]>
Cc: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi Alex,
On Fri, Mar 13, 2009 at 12:43 AM, Alexander Dunlap
<[email protected]> wrote:
> Isn't maximum always (semantically) strict anyway? I.e.
>
> maximum [1,2,undefined] = undefined
If max is (semantically) strict, then so is maximum.
On the other hand, both may be non-strict:
> data Switch = Off | On deriving (Eq, Show)
> instance Ord Switch where
> On <= Off = False
> _ <= _ = True
> max _ On = On
> max a Off = a
*Main> maximum [undefined,Off,On]
On
*Main> foldl1' max [undefined,Off,On]
*** Exception: Prelude.undefined
Best,
Roland
--
http://roland.zumkeller.googlepages.com/
------------------------------
Message: 4
Date: Fri, 13 Mar 2009 09:09:08 +0100
From: Chadda? Fouch? <[email protected]>
Subject: Re: [Haskell-beginners] maximum: stack overflow?
To: Roland Zumkeller <[email protected]>
Cc: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Fri, Mar 13, 2009 at 6:05 AM, Roland Zumkeller
<[email protected]> wrote:
> Hi Alex,
>
> On Fri, Mar 13, 2009 at 12:43 AM, Alexander Dunlap
> <[email protected]> wrote:
>> Isn't maximum always (semantically) strict anyway? I.e.
>>
>> maximum [1,2,undefined] = undefined
>
> If max is (semantically) strict, then so is maximum.
> On the other hand, both may be non-strict:
The case where max is not strict seldom happen and anyway in those
cases foldr1 would be more appropriate than foldl1 (which won't allow
fast termination, though a non-strict max may save you from stack
overflow)...
Note that with -O or -O2 you may have a specialization of maximum to
foldl1' if you're working on Int or Integer or ...
I guess the report really dropped the ball on this one with its
failure to settle on either lazyness or strictness.
--
Jedaï
------------------------------
Message: 5
Date: Fri, 13 Mar 2009 11:29:10 +0100
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: Integer factorization
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Francesco Bochicchio wrote:
> Heinrich Apfelmus wrote:
>>
>> Stylistically, one usually uses shorter variable names in Haskell.
>
> <beginner rant>
> Sometime too short peraphs? At least, this is one of the things that slows
> down my understanding of code posted
> on this list on or on various haskell tutorial. In any other language I
> know, programmers learn to give meaningful names to variable and functions,
> so when one reads a program, one can use the name to remember what the
> function does. Then one cames to haskell ...
> I guess the short names comes from mathematic background, but still ...
> haskell is already very succint - even more so
> when you use pointfree programming - and if one also uses names like a,e,i (
> look at Array function definitions ), ...
> </beginner rant>
>
> Rant apart, I notice that in my own excercises I tend to shorten names, so
> maybe there is a reason for that.
> Nevertheless readability tends to be a big issue in languages used in IT
> industry, and my feeling is that haskell
> tends to err on the laconic side of the balance.
The goal is of course to make code readable, that's why I recommend
short names. :D
Abstraction is the one driving force for very short names. For example,
take the definition of foldr
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Since this function is polymorphic, so f , z and the xs can be
anything, using more "descriptive" variable names is simply not
possible; the key point of fold is its generality.
A second, and my main reason for short names, or rather against long
names, is that names should be to the point. None of the names
newPrimes
topPrime
doFactors
doFilter
accurately describe the object they represent. The primes are not "new",
the prime is not "on top". The "do" is a prefix does not carry a meaning
either, it just conveys that doFactors has something to do with
factors . This is best expressed by making doFactors a local
definition in the where-block of factors .
The name eratosthenesFilter is ok, but since there is no other
eratosthenes around, no meaning is lost by shortening it to simply
eratosthenes . Not to mention that the conventional term is "sieve", not
"filter". The documentation has to elaborate on it anyway.
The generality of the name num hints that a single letter name is
preferable.
The names that I think are great because they are to the point are
factors
primes
> Out of curiosity, there is any reason why you called the auxiliary function
> 'go' ?
Convention. Often, an auxiliary function that does basically the same
thing as the main function factors but with an extra parameter will be
named factors' . The apostrophe has the drawback that it's easy to
forget, so some people now name such auxiliary functions go instead.
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 6
Date: Fri, 13 Mar 2009 11:48:30 +0100
From: "Sergey V. Mikhanov" <[email protected]>
Subject: Re: [Haskell-beginners] Re: Integer factorization
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Greetings!
> A second, and my main reason for short names, or rather against long
> names, is that names should be to the point. None of the names
>
> newPrimes
> topPrime
> doFactors
> doFilter
>
> accurately describe the object they represent. The primes are not "new",
> the prime is not "on top". The "do" is a prefix does not carry a meaning
> either, it just conveys that doFactors has something to do with
> factors . This is best expressed by making doFactors a local
> definition in the where-block of factors.
>
Those remarks are fine with me! I asked about the stylistic changes because
I came from the, hm, Java world and would like to avoid "writing familiar
things in unfamiliar language". In Java, factors() and doFactors() would be
a perfectly named methods: factors() is public, auxiliary doFactors() is
private and essentially _does_ the factoring.
> > Out of curiosity, there is any reason why you called the auxiliary
> function
> > 'go' ?
>
> Convention. Often, an auxiliary function that does basically the same
> thing as the main function factors but with an extra parameter will be
> named factors' . The apostrophe has the drawback that it's easy to
> forget, so some people now name such auxiliary functions go instead.
>
I think having a local function 'go' in 'factors' is aboslutely plausible:
it is local, there's no ambiguity.
Regards,
Sergey
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090313/74eea645/attachment-0001.htm
------------------------------
Message: 7
Date: Fri, 13 Mar 2009 11:58:17 +0100 (CET)
From: "Leslie P. Polzer" <[email protected]>
Subject: [Haskell-beginners] Longest common subsequence
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain;charset=utf-8
Hi,
after the factorial function I tried to write my second Haskell
program, tackling the longest common subsequence algorithm:
lcsList :: [a] -> [a] -> [a]
lcsList [] _ = []
lcsList _ [] = []
lcsList (x:xs) (y:ys) = if x == y
then lcsList xs ys
else
let lcs1 = lcsList x:xs ys
lcs2 = lcsList xs y:ys
in if (length lcs1) > (length lcs2)
then lcs1
else lcs2
main = do
putStrLn("Result: " show lcsList [1,2,3] [1,3])
GHC has several problems with it:
lcs.hs:4:27:
Could not deduce (Eq a) from the context ()
arising from a use of `==' at lcs.hs:4:27-32
Possible fix:
add (Eq a) to the context of the type signature for `lcsList'
I understand that I need to specify that type 'a' needs to
be a derived type of something that can be compared, but
how do I specify this in the code?
On a related note, how can I make the function more flexible,
to discern between case-sensitive and case-insensitive string
comparison, for example?
In Lisp I would just write this lambda list:
(defun lcs-list (list1 list2 &key (test #'eql))
...)
and it would allow me to specify the test but use some sensible
default if I don't.
And two other errors which I don't quite get:
lcs.hs:7:50:
Couldn't match expected type `[a] -> [[a1] -> [a1]]'
against inferred type `[a]'
In the second argument of `(:)', namely `xs ys'
In the expression: lcsList x : xs ys
In the definition of `lcs1': lcs1 = lcsList x : xs ys
lcs.hs:8:33:
Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `lcs2'
In the expression:
let
lcs1 = lcsList x : xs ys
lcs2 = lcsList xs y : ys
in if (length lcs1) > (length lcs2) then lcs1 else lcs2
in if (length lcs1) > (length lcs2) then lcs1 else lcs2
Can you help me with that?
Thanks,
Leslie
--
LinkedIn Profile: http://www.linkedin.com/in/polzer
Xing Profile: https://www.xing.com/profile/LeslieP_Polzer
Blog: http://blog.viridian-project.de/
------------------------------
Message: 8
Date: Fri, 13 Mar 2009 11:25:18 +0000
From: Colin Paul Adams <[email protected]>
Subject: Re: [Haskell-beginners] Re: Integer factorization
To: Heinrich Apfelmus <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>>>>> "Heinrich" == Heinrich Apfelmus <[email protected]> writes:
Heinrich> Abstraction is the one driving force for very short
Heinrich> names. For example, take the definition of foldr
Heinrich> foldr f z [] = z foldr f z (x:xs) = f x (foldr f z
Heinrich> xs)
Heinrich> Since this function is polymorphic, so f , z and the xs
Heinrich> can be anything, using more "descriptive" variable names
Heinrich> is simply not possible; the key point of fold is its
Heinrich> generality.
Wouldn't unit be a better descriptive name than z?
--
Colin Adams
Preston Lancashire
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 14
****************************************
