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 ****************************************