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: Re: Integer factorization (Colin Paul Adams)
2. Re: Integer factorization (David Frey)
3. strange take result--explanation? (7stud)
4. Re: strange take result--explanation? (7stud)
5. Re: Re: strange take result--explanation? (Francesco Bochicchio)
6. Re: Re: strange take result--explanation? (Francesco Bochicchio)
7. Re: Re: strange take result--explanation? (Brent Yorgey)
8. Re: strange take result--explanation? (Heinrich Apfelmus)
9. maximum: stack overflow? (Patrick LeBoutillier)
----------------------------------------------------------------------
Message: 1
Date: Wed, 11 Mar 2009 10:16:16 +0000
From: Colin Paul Adams <co...@colina.demon.co.uk>
Subject: Re: [Haskell-beginners] Re: Integer factorization
To: Francesco Bochicchio <bieff...@gmail.com>
Cc: Heinrich Apfelmus <apfel...@quantentunnel.de>,
beginners@haskell.org
Message-ID: <m3bps8xt3j....@colina.demon.co.uk>
Content-Type: text/plain; charset=us-ascii
>>>>> "Francesco" == Francesco Bochicchio <bieff...@gmail.com> writes:
Francesco> Nevertheless readability tends to be a big issue in
Francesco> languages used in IT industry, and my feeling is that
Francesco> haskell tends to err on the laconic side of the
Francesco> balance.
Strongly seconded.
--
Colin Adams
Preston Lancashire
------------------------------
Message: 2
Date: Wed, 11 Mar 2009 11:55:50 -0800
From: "David Frey" <dpf...@shaw.ca>
Subject: Re: [Haskell-beginners] Integer factorization
To: "Sergey V. Mikhanov" <ser...@mikhanov.com>, "beginners"
<beginners@haskell.org>
Message-ID: <uury5zdq.1236801350.6011060.df...@localhost>
Content-Type: text/plain; charset=ISO-8859-1
On 3/10/2009, "Sergey V. Mikhanov" <ser...@mikhanov.com> wrote:
> Hello,
>
>I am solving a problem of finding the largest prime factor of
>600851475143 (Project Euler is great for learning new language!), and
>came with the following solution (it uses the most ineffective
>approach to finding prime numbers, however is able to factor the above
>number in fraction of second):
>
>factors :: Integer -> [Integer]
>
>factors n = doFactors n (eratosthenesFilter [1..n])
>
>doFactors n primes
> | null newPrimes = []
> | otherwise =
> let topPrime = head newPrimes in
> if topPrime == n
> then [topPrime]
> else topPrime : (doFactors (n `quot` topPrime) primes)
> where
> newPrimes = snd $ break (\x -> (n `rem` x) == 0) primes
>
>eratosthenesFilter :: [Integer] -> [Integer]
>
>eratosthenesFilter [] = []
>eratosthenesFilter (num : nums)
> | num == 1 = eratosthenesFilter nums
> | otherwise = num : (eratosthenesFilter $ doFilter num nums)
> where
> doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums
>
>What would you do different (including stylistic changes)? What are
>the general comments about efficiency (not of the algorithm, but of
>the implementation: for example, is it fine to use break at every
>invocation of doFactors?) and elegance of the solution?
>
>Thanks and regards,
>Sergey
This is my solution to the same problem. I'm just a beginner with
Haskell as well, so just consider this as an alternate solution, not an
ideal solution.
The bottom 2 functions were pulled out of support code that I use for all
my Project Euler solutions, so that's why they seem unnecessarily
generic.
I think the only real advantages of my solution over yours is that I take
advantage of the fact that primes are always odd (except for the number
2) and that the largest prime factor of a number will always be <= half
its value.
main = putStrLn output
output = show result
result = largestPrimeFactor 600851475143
largestPrimeFactor n = last $ primeFactors n
{-
- Gets the prime factors of an integer.
-}
primeFactors :: (Integral a) => a -> [a]
primeFactors n = primeFactorsUsingPrimesList (2:[3, 5 .. n `div` 2]) n
{-
- Gets the prime factors of a number. The primes list passed as the
first
- argument is not required to be a list of primes. It is simply
required to be
- a list of values to try to divide the input from. If this list
contains
- non-prime values, they should be ordered. If the list does not
contain all
- of the primes that are divisors of the input value, then the result
will be
- incorrect.
-}
primeFactorsUsingPrimesList :: (Integral a) => [a] -> a -> [a]
primeFactorsUsingPrimesList _ 1 = []
primeFactorsUsingPrimesList (x:xs) n = if n `rem` x == 0
then x : primeFactorsUsingPrimesList (x:xs) (n `div` x)
else primeFactorsUsingPrimesList xs n
primeFactorsUsingPrimesList [] n = [n]
------------------------------
Message: 3
Date: Thu, 12 Mar 2009 08:11:46 +0000 (UTC)
From: 7stud <bbxx789_0...@yahoo.com>
Subject: [Haskell-beginners] strange take result--explanation?
To: beginners@haskell.org
Message-ID: <loom.20090312t080827-...@post.gmane.org>
Content-Type: text/plain; charset=us-ascii
*Main> let x = []
*Main> take (length x - 1) [1, 2, 3]
[]
*Main> length x
0
*Main> take (0 - 1) [1, 2, 3]
[]
*Main> take -1 [1, 2, 3]
<interactive>:1:0:
No instance for (Num (Int -> [a] -> [a]))
arising from a use of `-' at <interactive>:1:0-16
Possible fix:
add an instance declaration for (Num (Int -> [a] -> [a]))
In the expression: take - 1 [1, 2, 3]
In the definition of `it': it = take - 1 [1, 2, 3]
<interactive>:1:6:
No instance for (Num ([t] -> Int -> [a] -> [a]))
arising from the literal `1' at <interactive>:1:6-16
Possible fix:
add an instance declaration for (Num ([t] -> Int -> [a] -> [a]))
In the second argument of `(-)', namely `1 [1, 2, 3]'
In the expression: take - 1 [1, 2, 3]
In the definition of `it': it = take - 1 [1, 2, 3]
*Main> take - 1 [1, 2, 3]
-----
Why does
take (0 - 1) [1, 2, 3]
produce a result but not
take -1 [1, 2, 3]
? Thanks
------------------------------
Message: 4
Date: Thu, 12 Mar 2009 08:14:41 +0000 (UTC)
From: 7stud <bbxx789_0...@yahoo.com>
Subject: [Haskell-beginners] Re: strange take result--explanation?
To: beginners@haskell.org
Message-ID: <loom.20090312t081313-...@post.gmane.org>
Content-Type: text/plain; charset=us-ascii
7stud <bbxx789_05ss <at> yahoo.com> writes:
>
> Why does
>
> take (0 - 1) [1, 2, 3]
>
> produce a result but not
>
> take -1 [1, 2, 3]
>
> ? Thanks
>
Well, immediately after I hit the submit button, I thought I'd try this:
*Main> take (-1) [1, 2, 3]
[]
So why are the parentheses needed there?
------------------------------
Message: 5
Date: Thu, 12 Mar 2009 10:02:28 +0100
From: Francesco Bochicchio <bieff...@gmail.com>
Subject: Re: [Haskell-beginners] Re: strange take result--explanation?
To: beginners <beginners@haskell.org>
Message-ID:
<a6e7dd140903120202v4fdb9bafxe03963bf05831...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
2009/3/12 7stud <bbxx789_0...@yahoo.com>
> 7stud <bbxx789_05ss <at> yahoo.com> writes:
> >
> > Why does
> >
> > take (0 - 1) [1, 2, 3]
> >
> > produce a result but not
> >
> > take -1 [1, 2, 3]
> >
> > ? Thanks
> >
>
> Well, immediately after I hit the submit button, I thought I'd try this:
>
> *Main> take (-1) [1, 2, 3]
> []
>
> So why are the parentheses needed there?
>
>
>
I think because take -1 [1,2,3] is parsed as (take - 1 ) [1,2,3] or
something like that.
If you look to the error message, and translate the haskellese in plain
english, it says so.
"In the second argument of `(-)', namely `1 [1, 2, 3]' " :
so it looks like is looking for the two arguments of infix operator (-), the
first being 'take'.
But I don't understand because it says that 1 [1,2,3] is a single
argument...
"In the definition of `it': it = take - 1 [1, 2, 3]"
notice the blank between the minus sign and 1: even if you write -1, it
understands - 1.
So, ghc is trying to be helpful here :-)
Ciao
-----
FB
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090312/596510f8/attachment-0001.htm
------------------------------
Message: 6
Date: Thu, 12 Mar 2009 10:08:39 +0100
From: Francesco Bochicchio <bieff...@gmail.com>
Subject: Re: [Haskell-beginners] Re: strange take result--explanation?
To: beginners <beginners@haskell.org>
Message-ID:
<a6e7dd140903120208u27058babm59abc7d8cd9a4...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
>
> But I don't understand because it says that 1 [1,2,3] is a single
> argument...
>
Oh yes, because sintactically it looks like you want to apply the function
'1' to the argument '[1,2,3]',
the result being '1 [1,2,3]'
Ciao again
-----------
FB
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090312/6317ffea/attachment-0001.htm
------------------------------
Message: 7
Date: Thu, 12 Mar 2009 08:45:08 -0400
From: Brent Yorgey <byor...@seas.upenn.edu>
Subject: Re: [Haskell-beginners] Re: strange take result--explanation?
To: beginners@haskell.org
Message-ID: <20090312124508.ga32...@seas.upenn.edu>
Content-Type: text/plain; charset=us-ascii
On Thu, Mar 12, 2009 at 08:14:41AM +0000, 7stud wrote:
> 7stud <bbxx789_05ss <at> yahoo.com> writes:
> >
> > Why does
> >
> > take (0 - 1) [1, 2, 3]
> >
> > produce a result but not
> >
> > take -1 [1, 2, 3]
> >
> > ? Thanks
> >
>
> Well, immediately after I hit the submit button, I thought I'd try this:
>
> *Main> take (-1) [1, 2, 3]
> []
>
> So why are the parentheses needed there?
Negative numbers are a rather ugly corner of the Haskell lexical
specification. Indeed, without the parentheses, Haskell thinks you
are trying to use subtraction. Just always use parentheses around
negative numbers and you'll be fine. =)
-Brent
------------------------------
Message: 8
Date: Thu, 12 Mar 2009 13:48:58 +0100
From: Heinrich Apfelmus <apfel...@quantentunnel.de>
Subject: [Haskell-beginners] Re: strange take result--explanation?
To: beginners@haskell.org
Message-ID: <gpb09n$dq...@ger.gmane.org>
Content-Type: text/plain; charset=ISO-8859-1
Francesco Bochicchio wrote:
>> But I don't understand because it says that 1 [1,2,3] is a single
>> argument...
>>
>
> Oh yes, because syntactically it looks like you want to apply the function
> '1' to the argument '[1,2,3]',
> the result being '1 [1,2,3]'
Yes, the error messages indicate that GHC is parsing the expression as
(take) - (1 [1,2,3])
and consequently complains that
take :: Int -> [a] -> [a]
is not a number (i.e. an instance of class Num) and that it can't
interpret the inferred type of
1 :: [t] -> (type of take)
as a Num .
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 9
Date: Thu, 12 Mar 2009 22:35:11 -0400
From: Patrick LeBoutillier <patrick.leboutill...@gmail.com>
Subject: [Haskell-beginners] maximum: stack overflow?
To: beginners <beginners@haskell.org>
Message-ID:
<b217a64f0903121935m5350432n5cea972fa6fc3...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Hi all,
Why does finding the maximum element of a big list cause a stack overflow:
In ghci, if I print out a big list:
*Main> [1..1000000]
it takes a while but it prints. However, looking for the maximum element fails:
*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?
Patrick
--
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 13
****************************************
