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: Resources to learn functional programming (Patrick Redmond)
2. Re: Resources to learn functional programming
(Homero Cardoso de Almeida)
3. Re: Resources to learn functional programming
(Alexander Bernauer)
4. vector indexing time (Ivan Vyalov)
5. Re: vector indexing time (Alexander Dunlap)
6. Re: vector indexing time (Nick Vanderweit)
----------------------------------------------------------------------
Message: 1
Date: Thu, 2 Aug 2012 06:30:26 -0400
From: Patrick Redmond <plredm...@gmail.com>
Subject: Re: [Haskell-beginners] Resources to learn functional
programming
To: Haskell Beginners <beginners@haskell.org>
Message-ID:
<cahuea4h4lav2gcrnw_uhr43lqbqksuajfyowyhfczt8mizm...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Although many resources have been mentioned here, I'd like to
recommend "How To Design Programs", <http://www.htdp.org/>, which
approaches functional programming from a Scheme (Racket) perspective.
This book is how I learned functional programming and developed an
interest in Haskell.
In HTDP, higher order functions aren't introduced until you've been
taught how to write similar code without them. Then you learn that
your code can be abbreviated using things like map, foldl, foldr,
ormap, andmap, etc. The book moves into more complicated uses of
functions-as-data near the end.
Hope you find it useful,
Patrick
On Thu, Aug 2, 2012 at 4:03 AM, Arthur Clune <art...@clune.org> wrote:
> In a similar vein, I highly recommend "Higher Order Perl" by
> Mark-Jason Dominus. It presents most of these concepts in a more
> familiar setting. Don't worry if you don't know perl, if you know C++,
> you'll know enough to follow the book.
>
> Arthur
>
> --
> Arthur Clune art...@clune.org
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 2
Date: Thu, 2 Aug 2012 10:54:16 -0300
From: Homero Cardoso de Almeida <homero...@gmail.com>
Subject: Re: [Haskell-beginners] Resources to learn functional
programming
To: Patrick Redmond <plredm...@gmail.com>
Cc: Haskell Beginners <beginners@haskell.org>
Message-ID:
<CAPv0Zwop0eUZj999E2uZQiyTN3VN3aqJEWWMNZKQHP7ty=n...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Thanks for all the suggestions.
I was learning Haskell through LYAHFGG, and that's when I got the problem
with Higher Order functions. I'll take a look at all the resources posted.
Thanks again,
Homero Cardoso de Almeida
On Thu, Aug 2, 2012 at 7:30 AM, Patrick Redmond <plredm...@gmail.com> wrote:
> Although many resources have been mentioned here, I'd like to
> recommend "How To Design Programs", <http://www.htdp.org/>, which
> approaches functional programming from a Scheme (Racket) perspective.
> This book is how I learned functional programming and developed an
> interest in Haskell.
>
> In HTDP, higher order functions aren't introduced until you've been
> taught how to write similar code without them. Then you learn that
> your code can be abbreviated using things like map, foldl, foldr,
> ormap, andmap, etc. The book moves into more complicated uses of
> functions-as-data near the end.
>
> Hope you find it useful,
> Patrick
>
>
> On Thu, Aug 2, 2012 at 4:03 AM, Arthur Clune <art...@clune.org> wrote:
> > In a similar vein, I highly recommend "Higher Order Perl" by
> > Mark-Jason Dominus. It presents most of these concepts in a more
> > familiar setting. Don't worry if you don't know perl, if you know C++,
> > you'll know enough to follow the book.
> >
> > Arthur
> >
> > --
> > Arthur Clune art...@clune.org
> >
> > _______________________________________________
> > Beginners mailing list
> > Beginners@haskell.org
> > http://www.haskell.org/mailman/listinfo/beginners
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120802/b7a6a76f/attachment-0001.htm>
------------------------------
Message: 3
Date: Thu, 2 Aug 2012 16:19:01 +0200
From: Alexander Bernauer <alex-hask...@copton.net>
Subject: Re: [Haskell-beginners] Resources to learn functional
programming
To: beginners@haskell.org
Message-ID: <20120802141901.GB2608@apus>
Content-Type: text/plain; charset="us-ascii"
On Wed, Aug 01, 2012 at 05:53:36PM -0300, Homero Cardoso de Almeida wrote:
> I'm trying to learn it, but got stuck when i reached high-order functions.
> [...]
> I am a decent C++ programmer.
The C++ analogy is as follows: a high-order function is a function that
takes a parameter of a type that has an operator() defined (or returns
a value of such a type).
For example, find_if [1] is such a "high-order function".
---8<---
struct T { int i; };
class Predicate {
public:
bool operator()(const T& t) { return t.i == 23; }
};
std::vector<T> ts;
bool has23() {
Predicate pred;
return find_if(ts.begin(), ts.end(), pred) != ts.end();
}
--->8---
In Haskell the analogous example would be:
---8<---
data T = T Int
pred :: T -> Bool
pred (T i) = i == 23
ts :: [T]
has23 :: Bool
has23 = isJust $ find pred ts
--->8---
HTH
Alex
[1] http://www.sgi.com/tech/stl/find_if.html
-------------- 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/20120802/09244bcf/attachment-0001.pgp>
------------------------------
Message: 4
Date: Fri, 03 Aug 2012 04:45:38 +0400
From: Ivan Vyalov <vyalovi...@yandex.ru>
Subject: [Haskell-beginners] vector indexing time
To: beginners@haskell.org
Message-ID: <114041343954...@web21h.yandex.ru>
Content-Type: text/plain
Hi everyone!
I have a question about time complexity of vector indexing. Obviously, it
should be constant, but if I do the following naive tests it looks linear. What
do I do wrong?
Ivan
$ for i in 10000000 20000000 40000000 80000000 ; do cat vec_in_"$i".hs; ghc
-fforce-recomp -O2 --make vec_in_"$i".hs && time ./vec_in_"$i"; done
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ a ! 10000000
[1 of 1] Compiling Main ( vec_in_10000000.hs, vec_in_10000000.o )
Linking vec_in_10000000 ...
10000001
real 0m0.033s
user 0m0.032s
sys 0m0.000s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ a ! 20000000
[1 of 1] Compiling Main ( vec_in_20000000.hs, vec_in_20000000.o )
Linking vec_in_20000000 ...
20000001
real 0m0.062s
user 0m0.060s
sys 0m0.000s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ a ! 40000000
[1 of 1] Compiling Main ( vec_in_40000000.hs, vec_in_40000000.o )
Linking vec_in_40000000 ...
40000001
real 0m0.125s
user 0m0.120s
sys 0m0.004s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ a ! 80000000
[1 of 1] Compiling Main ( vec_in_80000000.hs, vec_in_80000000.o )
Linking vec_in_80000000 ...
80000001
real 0m0.244s
user 0m0.240s
sys 0m0.000s
------------------------------
Message: 5
Date: Thu, 2 Aug 2012 22:13:47 -0500
From: Alexander Dunlap <alexander.dun...@gmail.com>
Subject: Re: [Haskell-beginners] vector indexing time
To: Ivan Vyalov <vyalovi...@yandex.ru>
Cc: beginners@haskell.org
Message-ID:
<cakdsjnftrhvkhz1mahcw-c2e4_v11tqspjobbixf+mnomog...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On 2 August 2012 19:45, Ivan Vyalov <vyalovi...@yandex.ru> wrote:
> Hi everyone!
>
> I have a question about time complexity of vector indexing. Obviously, it
> should be constant, but if I do the following naive tests it looks linear.
> What do I do wrong?
>
>
> Ivan
>
>
> $ for i in 10000000 20000000 40000000 80000000 ; do cat vec_in_"$i".hs; ghc
> -fforce-recomp -O2 --make vec_in_"$i".hs && time ./vec_in_"$i"; done
> import Data.Vector.Unboxed
> main = do
> let a = enumFromN 1 100000001 :: Vector Int
> print $ a ! 10000000
>
> [1 of 1] Compiling Main ( vec_in_10000000.hs, vec_in_10000000.o )
> Linking vec_in_10000000 ...
> 10000001
>
> real 0m0.033s
> user 0m0.032s
> sys 0m0.000s
> import Data.Vector.Unboxed
> main = do
> let a = enumFromN 1 100000001 :: Vector Int
> print $ a ! 20000000
>
> [1 of 1] Compiling Main ( vec_in_20000000.hs, vec_in_20000000.o )
> Linking vec_in_20000000 ...
> 20000001
>
> real 0m0.062s
> user 0m0.060s
> sys 0m0.000s
> import Data.Vector.Unboxed
> main = do
> let a = enumFromN 1 100000001 :: Vector Int
> print $ a ! 40000000
>
> [1 of 1] Compiling Main ( vec_in_40000000.hs, vec_in_40000000.o )
> Linking vec_in_40000000 ...
> 40000001
>
> real 0m0.125s
> user 0m0.120s
> sys 0m0.004s
> import Data.Vector.Unboxed
> main = do
> let a = enumFromN 1 100000001 :: Vector Int
> print $ a ! 80000000
>
> [1 of 1] Compiling Main ( vec_in_80000000.hs, vec_in_80000000.o )
> Linking vec_in_80000000 ...
> 80000001
>
> real 0m0.244s
> user 0m0.240s
> sys 0m0.000s
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
I'm no expert, but I suspect it has something to do with stream fusion
and the entire vector thus not being generated when you only ask for
an early element. The time difference went away when I modified your
code to also print the length of the vector. Also, when I compiled
without optimization, there were only negligible differences between
the different runs.
Alex
$ for i in 10000000 20000000 40000000 80000000 ; do cat
vec_in_"$i".hs; ghc -fforce-recomp -O2 --make vec_in_"$i".hs && time
./vec_in_"$i"; done
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ Data.Vector.Unboxed.length a
print $ a ! 10000000
[1 of 1] Compiling Main ( vec_in_10000000.hs, vec_in_10000000.o )
Linking vec_in_10000000 ...
100000001
10000001
real 0m0.323s
user 0m0.100s
sys 0m0.220s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ Data.Vector.Unboxed.length a
print $ a ! 20000000
[1 of 1] Compiling Main ( vec_in_20000000.hs, vec_in_20000000.o )
Linking vec_in_20000000 ...
100000001
20000001
real 0m0.323s
user 0m0.130s
sys 0m0.190s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ Data.Vector.Unboxed.length a
print $ a ! 40000000
[1 of 1] Compiling Main ( vec_in_40000000.hs, vec_in_40000000.o )
Linking vec_in_40000000 ...
100000001
40000001
real 0m0.317s
user 0m0.117s
sys 0m0.197s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ Data.Vector.Unboxed.length a
print $ a ! 80000000
[1 of 1] Compiling Main ( vec_in_80000000.hs, vec_in_80000000.o )
Linking vec_in_80000000 ...
100000001
80000001
real 0m0.329s
user 0m0.133s
sys 0m0.193s
------------------------------
Message: 6
Date: Thu, 02 Aug 2012 21:20:29 -0600
From: Nick Vanderweit <nick.vanderw...@gmail.com>
Subject: Re: [Haskell-beginners] vector indexing time
To: beginners@haskell.org
Message-ID: <7388175.QrKvKZY0yM@euler>
Content-Type: text/plain; charset="us-ascii"
The vector indexing using (!) should run in constant time. However, as the
Data.Vector.Unboxed haddock documentation states, enumFromN allocates and
populates the vector in linear time using its stream code. I'm not familiar
with the stream code, but it looks to be of similar nature to the basic list
type.
Nick
On Friday, August 03, 2012 04:45:38 AM Ivan Vyalov wrote:
> Hi everyone!
>
> I have a question about time complexity of vector indexing. Obviously, it
> should be constant, but if I do the following naive tests it looks linear.
> What do I do wrong?
>
>
> Ivan
>
>
> $ for i in 10000000 20000000 40000000 80000000 ; do cat vec_in_"$i".hs; ghc
> -fforce-recomp -O2 --make vec_in_"$i".hs && time ./vec_in_"$i"; done import
> Data.Vector.Unboxed
> main = do
> let a = enumFromN 1 100000001 :: Vector Int
> print $ a ! 10000000
>
> [1 of 1] Compiling Main ( vec_in_10000000.hs, vec_in_10000000.o
> ) Linking vec_in_10000000 ...
> 10000001
>
> real 0m0.033s
> user 0m0.032s
> sys 0m0.000s
> import Data.Vector.Unboxed
> main = do
> let a = enumFromN 1 100000001 :: Vector Int
> print $ a ! 20000000
>
> [1 of 1] Compiling Main ( vec_in_20000000.hs, vec_in_20000000.o
> ) Linking vec_in_20000000 ...
> 20000001
>
> real 0m0.062s
> user 0m0.060s
> sys 0m0.000s
> import Data.Vector.Unboxed
> main = do
> let a = enumFromN 1 100000001 :: Vector Int
> print $ a ! 40000000
>
> [1 of 1] Compiling Main ( vec_in_40000000.hs, vec_in_40000000.o
> ) Linking vec_in_40000000 ...
> 40000001
>
> real 0m0.125s
> user 0m0.120s
> sys 0m0.004s
> import Data.Vector.Unboxed
> main = do
> let a = enumFromN 1 100000001 :: Vector Int
> print $ a ! 80000000
>
> [1 of 1] Compiling Main ( vec_in_80000000.hs, vec_in_80000000.o
> ) Linking vec_in_80000000 ...
> 80000001
>
> real 0m0.244s
> user 0m0.240s
> sys 0m0.000s
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 50, Issue 4
****************************************
