Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/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. Prime numbers -- specific list comprehension explained
(Alexander Chen)
2. Re: Prime numbers -- specific list comprehension explained
(Ut Primum)
3. Code review request? (Jake Vossen)
4. Re: Code review request? (Ut Primum)
----------------------------------------------------------------------
Message: 1
Date: Wed, 15 Jan 2020 15:41:00 +0100 (CET)
From: Alexander Chen <alexan...@chenjia.nl>
To: beginners@haskell.org
Subject: [Haskell-beginners] Prime numbers -- specific list
comprehension explained
Message-ID: <673337005.3058.1579099260...@ichabod.co-bxl>
Content-Type: text/plain; charset="utf-8"
Hi,
This could gives you for any given integer the list of prime numbers. source is
from a stack overflow snippet.
helper function:
isqrt :: Integral a => a -> a
isqrt = floor . sqrt . fromIntegral
main function:
primes 1 = []
primes n = 2:[i | i <- [3,5..n], and [mod i k /= 0 | k <- primes (isqrt i)]]
my main unclarity is how I should interpret i and k in de mod part. At every
step of the recursion.
example: primes 10.
it should generate [2,3,5,7,9] if you ignore the second part.
however, when I look at the second part
then first I need to do this primes (isqrt 10), which give primes 3. which
gives met [2,3].
first question) I haven't reached base case in this situations so can i or can
i not meaningfully evaluate mod i k /= 0?
Independent of that I now go deeper to reach base case.
So I go to primes (isqrt 3) which gives me primes 1 which is []. Now I hit the
base case and need to definitely evaluate mod i k /= 0.
second question) but in this case what is i and what is k?
If I have it completely wrong, then please be patience. I appreciate the input!
best,
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200115/14f014e5/attachment-0001.html>
------------------------------
Message: 2
Date: Wed, 15 Jan 2020 16:48:20 +0100
From: Ut Primum <utpri...@gmail.com>
To: Alexander Chen <alexan...@chenjia.nl>, The Haskell-Beginners
Mailing List - Discussion of primarily beginner-level topics related
to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Prime numbers -- specific list
comprehension explained
Message-ID:
<CANjDmKLRedcM3p7Ac=QxFJK3YyW=5swjdjrylrqztgu4brs...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi,
First I'll answer your second question:
but in this case what is i and what is k?
(So the question is about primes 3)
Think about the meaning of the expression primes 3, which is:
primes 3 = 2:[i | i <- [3,5..3], and [mod i k /= 0 | k <- primes (isqrt i)]]
= 2:*[i | i <- [3], and [mod i k /= 0 | k <- primes (isqrt
i)]] *
So, in the list *[i | i <- [3], and [mod i k /= 0 | k <- primes (isqrt
i)]]* i takes all values in the list *[3]* (i.e. it is only 3) and for
each of them the condition
*[mod i k /= 0 | k <- primes (isqrt i)] *
must be checked. When i=3, it is *[mod 3 k /= 0 | k <- primes 1] * = *
[mod 3 k /= 0 | k <- []]*, so the condition is empty (it means you must
check that mod 3 k is nonzero for every k in the empty list, so you don't
need to check anything!).
So this is clearly primes 3 = 2:*[3]* = [2,3].
To understand better, if you had:
[i | i <- [3,4,5,6], and [mod i k /= 0 | k <- []]]
(this never occurs in the program, but just to understand what i and k are)
i would be respectively 3,4,5 and 6 and for each i, k would be nothing. So
the list above is equal to [3,4,5,6].
Now maybe the meaning of this kind of expressions is mor clear, and you can
see that what you imagined the function did is not completely correct:
primes 10 = 2:[i | i <- [3,5,7,9], and [mod i k /= 0 | k <- primes (isqrt
i)]]
So, i is not 10 (so you don't always take k in primes 3), since it varies
among the values 3,5,7 and 9.
When i is 3, as I said before, k is in primes 1 = [], so there is no
further condition to check, so 3 is in the list.
When i is 5, k is in primes (isqrt 5) = primes 2 = [2], so you have to
check if mod 5 2 is nonzero, and it is, so 5 is in the list.
When i is 7, k is in primes (isqrt 7) = primes 2 = [2], so you have to
check if mod 7 2 is nonzero, and it is, so 7 is in the list.
When i is 9, k is in primes (isqrt 9) = primes 3 = [2,3], so you have to
check if mod 9 2 is nonzero and mod 9 3 is nonzero, but this is false, so 9
is NOT in the list.
As for your first question (which is now about something that happens for
i=9, not for i=10 which never happens, n=10, not i, so you never look at primes
(isqrt 10), but the answer would be the same, there is no difference)
I haven't reached base case in this situations so can i or can i not
meaningfully evaluate* mod i k /= 0*?
The answer is that of course you have to evaluate primes 3 before. So when
the expression is reduced, first primes 3 is calculated (and as you said it
gives [2,3]), and then mod i k /=0 can be evaluated because you know where
both i and k vary.
I hope it is clear,
cheers,
Ut
Il giorno mer 15 gen 2020 alle ore 15:49 Alexander Chen <
alexan...@chenjia.nl> ha scritto:
> Hi,
>
> This could gives you for any given integer the list of prime numbers.
> source is from a stack overflow snippet.
>
> helper function:
> isqrt :: Integral a => a -> a
> isqrt = floor . sqrt . fromIntegral
>
> main function:
> primes 1 = []
> primes n = 2:[i | i <- [3,5..n], and [mod i k /= 0 | k <- primes (isqrt
> i)]]
>
>
>
> my main unclarity is how I should interpret i and k in de mod part. At
> every step of the recursion.
>
> example: *primes 10*.
>
> it should generate *[2,3,5,7,9]* if you ignore the second part.
>
> however, when I look at the second part
>
> then first I need to do this *primes (isqrt 10)*, which give primes 3.
> which gives met *[2,3]*.
> first question) I haven't reached base case in this situations so can i or
> can i not meaningfully evaluate* mod i k /= 0*?
> Independent of that I now go deeper to reach base case.
> So I go to *primes (isqrt 3)* which gives me primes 1 which is *[]*. Now
> I hit the base case and need to definitely evaluate *mod i k /= 0.*
> second question) but in this case what is i and what is k?
>
> If I have it completely wrong, then please be patience. I appreciate the
> input!
>
> best,
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200115/16f0573e/attachment-0001.html>
------------------------------
Message: 3
Date: Wed, 15 Jan 2020 17:26:31 +0000
From: Jake Vossen <j...@vossen.dev>
To: beginners@haskell.org
Subject: [Haskell-beginners] Code review request?
Message-ID: <76a009d5-1586-5253-dd42-5c9bc1d63...@vossen.dev>
Content-Type: text/plain; charset="utf-8"
Hey everyone,
Let me know if this is not the right place for this, but I am curious if
someone could take a look at my code and maybe share some feedback / how
a more experienced haskeller would approach this problem.
New to Haskell, pretty experienced with imperative languages. I have
solved the following problem in Haskell:
> Given a non-empty array, return true if there is a place to split the
> array so that the sum of the numbers on one side is equal to the sum
> of the numbers on the other side.
> canBalance([1, 1, 1, 2, 1]) -> true
> canBalance([2, 1, 1, 2, 1]) -> false
> canBalance([10, 10]) -> true
Here is my code (my solution uses `can_split_even` not `canBalance`)
```
can_split_even :: (Num a) => (Eq a) => [a] -> Bool
can_split_even xs = True `elem` is_even_at_each_spot
where
is_even_at_each_spot :: [Bool]
is_even_at_each_spot = map (is_split xs) [1 .. (length xs - 1)]
where
is_split :: (Num a) => (Eq a) => [a] -> Int -> Bool
is_split xs index = sum (take index xs) == sum (drop index xs)
```
Thanks so much!
--
Jake Vossen
Colorado School of Mines, Class of 2022
B.S. Computer Science
PGP: 08CD 67DA FE3A 0AE7 B946 6AC3 B812 7052 D9E3 817B
https://jake.vossen.dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200115/2ba860f8/attachment-0001.sig>
------------------------------
Message: 4
Date: Wed, 15 Jan 2020 19:54:03 +0100
From: Ut Primum <utpri...@gmail.com>
To: Jake Vossen <j...@vossen.dev>, The Haskell-Beginners Mailing List
- Discussion of primarily beginner-level topics related to Haskell
<beginners@haskell.org>
Subject: Re: [Haskell-beginners] Code review request?
Message-ID:
<CANjDmKLRNcxLY-tQwQaAqByyOjmhNu=m3emywdwp7mufy3b...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi,
this is how I would have solved the exercise:
canBalanceRec [] _ _ = False
canBalanceRec (x:xs) s1 s2 = s1+x==s2-x || canBalanceRec xs (s1+x) (s2-x)
canBalance xs = s==0 || canBalanceRec xs 0 s where s=sum xs
Note that there is one difference: in this case
canBalance [-2,-2,4] = True
because I think I can split the list into [ ] and the rest (since the sum
of the empty list is 0 and the same is the sum of the elements of the
lists). Anyway this is a matter of how we interpret the text of the
exercise (your function would return False instead). Note that removing the
"s==0 ||" makes no difference.
An advantage of my solution is that it is less expensive, since its
computational complexity is linear in the length of the list xs. Yours uses
sum and drop many times, and so is slower. Just to have an idea of the
difference (using ghci interpreter):
> canBalance [1..10000]
False
(*0.02* secs, 6,974,552 bytes)
> can_split_even [1..10000]
False
(*5.60* secs, 11,395,843,384 bytes)
Cheers,
Ut
Il giorno mer 15 gen 2020 alle ore 18:27 Jake Vossen <j...@vossen.dev> ha
scritto:
> Hey everyone,
>
> Let me know if this is not the right place for this, but I am curious if
> someone could take a look at my code and maybe share some feedback / how
> a more experienced haskeller would approach this problem.
>
> New to Haskell, pretty experienced with imperative languages. I have
> solved the following problem in Haskell:
>
> > Given a non-empty array, return true if there is a place to split the
> > array so that the sum of the numbers on one side is equal to the sum
> > of the numbers on the other side.
>
> > canBalance([1, 1, 1, 2, 1]) -> true
> > canBalance([2, 1, 1, 2, 1]) -> false
> > canBalance([10, 10]) -> true
>
> Here is my code (my solution uses `can_split_even` not `canBalance`)
>
> ```
> can_split_even :: (Num a) => (Eq a) => [a] -> Bool
> can_split_even xs = True `elem` is_even_at_each_spot
> where
> is_even_at_each_spot :: [Bool]
> is_even_at_each_spot = map (is_split xs) [1 .. (length xs - 1)]
> where
> is_split :: (Num a) => (Eq a) => [a] -> Int -> Bool
> is_split xs index = sum (take index xs) == sum (drop index xs)
> ```
>
> Thanks so much!
>
> --
> Jake Vossen
> Colorado School of Mines, Class of 2022
> B.S. Computer Science
> PGP: 08CD 67DA FE3A 0AE7 B946 6AC3 B812 7052 D9E3 817B
> https://jake.vossen.dev
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200115/7eeb29ed/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 139, Issue 4
*****************************************
