https://wiki.haskell.org/api.php?action=feedcontributions&user=Leoncamel&feedformat=atomHaskellWiki - User contributions [en]2020-05-31T06:14:52ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Gtk2Hs/Mac&diff=44961Gtk2Hs/Mac2012-03-19T23:57:34Z<p>Leoncamel: /* Troubleshooting */</p>
<hr />
<div>== Known configurations ==<br />
<br />
{|<br />
!|Date<br />
!|Arch<br />
!|OS<br />
!|GTK<br />
!|Gtk2Hs<br />
!|GHC<br />
!|Haskell Platform<br />
|-<br />
|2012-02<br />
|Intel 64-bit<br />
|Lion - 10.7.3, Xcode 4.1<br />
|MacPorts<br />
|darcs HEAD 2012-02-20<br />
|7.4.1 (built from source, 64-bit)<br />
|<br />
|-<br />
|2011-08<br />
|Intel 32-bit<br />
|Snow Leopard<br />
|2.24.5 Homebrew<br />
|gtk-0.12.0<br />
|7.0.3<br />
|2011.2.0.1<br />
|-<br />
|2011-03<br />
|Intel 64-bit<br />
|Leopard<br />
|MacPorts<br />
|<br />
|6.10<br />
|<br />
|}<br />
<br />
== HomeBrew (last checked 2011-08) ==<br />
<br />
<pre><br />
brew update <br />
brew install gtk+ libglade<br />
gtk-demo<br />
</pre><br />
If the gtk-demo appears to work, proceed to the rest of the ThreadScope install.<br />
<br />
=== Troubleshooting ===<br />
<br />
Problem: Bus error<br />
<br />
Try running the gtk-demo program. Does it also fail?<br />
<br />
If so, did you try updating your port? For example, if you are using Howebrew try:<br />
<br />
<pre><br />
brew update<br />
brew install gtk+<br />
</pre><br />
<br />
Then try gtk-demo again and finally<br />
<br />
<pre>cabal install --renistall gtk</pre><br />
<br />
It may be worthwhile to try a [http://projects.haskell.org/gtk2hs/documentation/#hello_world gtkhs helloworld]<br />
<br />
== MacPorts (last checked 2011-03-10) ==<br />
<br />
* Install [http://www.macports.org/ MacPorts]<br />
* Add <tt>+universal</tt> to <tt>/opt/local/etc/macports/variants.conf</tt> (not needed on 32bit)<br />
* execute:<pre>sudo port install ghc gtk2 gvfs cairo librsvg libglade2 gtkglext gtksourceview2 && sudo port install gtk2hs -universal</pre><br />
<br />
=== Detailed instructions ===<br />
<br />
This explains how to install Gtk2Hs-0.10.1 on Mac OS X 10.6 Snow Leopard, in combination with GTK+ from MacPorts.<br />
<br />
* Install the [http://hackage.haskell.org/platform/ Haskell Platform] for Mac<br />
* Download gtk2hs from [http://www.haskell.org/gtk2hs/ Gtk2Hs website] and untar it.<br />
* Install gtk, cairo, etc. from MacPorts like this (note that the <tt>+universal</tt> is needed; if you already installed gtk or one of its dependencies, it is recommended you reinstall those as detailed in the NB at the end of this section).<br />
<pre>sudo port install gtk +universal</pre><br />
* Go to the directory where gtk2hs is untarred and run<br />
<pre>./configure --disable-split-objs --disable-gio<br />
make<br />
sudo make install</pre><br />
<br />
Alternatively, if you wish to follow the Mac OS X style of directory layout, you can use this configure command instead:<br />
<pre>./configure --with-pkgconf=/Users/$USER/.ghc/i386-darwin-6.10.4/package.conf --prefix=/Users/$USER/Library/Haskell/packages/gtk2hs --disable-split-objs --disable-gio</pre><br />
<br />
Right now you should be able to run the demos. Unfortunately, to build any libraries depending on Gtk2Hs, such as [http://hackage.haskell.org/package/Chart/ Chart], you need to edit one more file. You will need to find <tt>package.conf</tt> for your installed GHC by running<br />
<br />
<pre>ghc-pkg list</pre><br />
<br />
In the output you will see the full directory to your <tt>package.conf</tt> file. In this file, you need to search for "gthread", and everywhere you can find it, add <tt>"/opt/local/lib"</tt> (with quotes) to the <tt>libraryDirs</tt> array before it.<br />
<br />
If all went well, it should be properly installed now.<br />
<br />
NB: If compiling fails with architecture errors for certain dynlibs, you need to reinstall the packages these dynlibs belong to with <tt>+universal</tt> by doing<br />
<br />
<pre>sudo port upgrade packagename --enforce-variants +universal</pre><br />
<br />
Alternatively, and this is recommended, you can follow the steps on [http://passingcuriosity.com/2009/haskell-on-snow-leopard/ Haskell On Snow Leopard Blogpost] to immediately add the universal variant of each package:<br />
# Edit <tt>/opt/local/macports/variants.conf</tt> and add <tt>+universal</tt> to the end of this file<br />
# sudo port selfupdate <br />
# sudo port sync<br />
# sudo port upgrade --force installed<br />
<br />
== GTK+ OS X Framework ==<br />
<br />
This explains how to install Gtk2Hs on Macs using the native [http://gtk-osx.sourceforge.net/ GTK+ OS X Framework], a port of GTK+ to the Mac that does '''not''' depend on X11, and hence, is better integrated into the Mac desktop - i.e., menus actually appear in the menu bar, where they belong. It also avoids the often tedious installation of GTK+ via MacPorts. However, it misses support for optional Gtk2Hs packages that are currently not supported by the [http://gtk-osx.sourceforge.net/ GTK+ OS X Framework], most notably support for Glade. It does include support for Cairo, though.<br />
<br />
Here is how to install the library:<br />
# Download and install [http://gtk-osx.sourceforge.net/ GTK+ OS X Framework] (this uses the standard Mac package installer).<br />
# Install [http://pkg-config.freedesktop.org/ pkg-config], either by compiling it from source or via MacPorts.<br />
# Download and unpack the Gtk2Hs tar ball from the [http://www.haskell.org/gtk2hs/download/ Gtk2Hs download page] (I tested 0.10.0).<br />
# Configure with (you may want to remove the two backslashes and put everything on one line)<br />
env PKG_CONFIG_PATH=/Library/Frameworks/Cairo.framework/Resources/dev/lib/pkgconfig:\ <br />
/Library/Frameworks/GLib.framework/Resources/dev/lib/pkgconfig:\ <br />
/Library/Frameworks/Gtk.framework/Resources/dev/lib/pkgconfig ./configure --disable-gio<br />
# Build with<br />
make<br />
# Install (to <tt>/usr/local/</tt> unless a <tt>--prefix</tt> option was passed to <tt>configure</tt>) with<br />
sudo make install<br />
<br />
The library is now registered with the package database of the GHC you used for compiling.<br />
<br />
NB: Thanks to Ross Mellgren for his post on the gtk2hs-users list that outlined the use of <tt>PKG_CONFIG_PATH</tt>.</div>Leoncamelhttps://wiki.haskell.org/index.php?title=Gtk2Hs/Mac&diff=44960Gtk2Hs/Mac2012-03-19T23:56:58Z<p>Leoncamel: /* Troubleshooting */</p>
<hr />
<div>== Known configurations ==<br />
<br />
{|<br />
!|Date<br />
!|Arch<br />
!|OS<br />
!|GTK<br />
!|Gtk2Hs<br />
!|GHC<br />
!|Haskell Platform<br />
|-<br />
|2012-02<br />
|Intel 64-bit<br />
|Lion - 10.7.3, Xcode 4.1<br />
|MacPorts<br />
|darcs HEAD 2012-02-20<br />
|7.4.1 (built from source, 64-bit)<br />
|<br />
|-<br />
|2011-08<br />
|Intel 32-bit<br />
|Snow Leopard<br />
|2.24.5 Homebrew<br />
|gtk-0.12.0<br />
|7.0.3<br />
|2011.2.0.1<br />
|-<br />
|2011-03<br />
|Intel 64-bit<br />
|Leopard<br />
|MacPorts<br />
|<br />
|6.10<br />
|<br />
|}<br />
<br />
== HomeBrew (last checked 2011-08) ==<br />
<br />
<pre><br />
brew update <br />
brew install gtk+ libglade<br />
gtk-demo<br />
</pre><br />
If the gtk-demo appears to work, proceed to the rest of the ThreadScope install.<br />
<br />
=== Troubleshooting ===<br />
<br />
Problem: Bus error<br />
<br />
Try running the gtk-demo program. Does it also fail?<br />
<br />
If so, did you try updating your port? For example, if you are using Howebrew try:<br />
<br />
<pre>brew update</pre><br />
<pre>brew install gtk+</pre><br />
<br />
Then try gtk-demo again and finally<br />
<br />
<pre>cabal install --renistall gtk</pre><br />
<br />
It may be worthwhile to try a [http://projects.haskell.org/gtk2hs/documentation/#hello_world gtkhs helloworld]<br />
<br />
== MacPorts (last checked 2011-03-10) ==<br />
<br />
* Install [http://www.macports.org/ MacPorts]<br />
* Add <tt>+universal</tt> to <tt>/opt/local/etc/macports/variants.conf</tt> (not needed on 32bit)<br />
* execute:<pre>sudo port install ghc gtk2 gvfs cairo librsvg libglade2 gtkglext gtksourceview2 && sudo port install gtk2hs -universal</pre><br />
<br />
=== Detailed instructions ===<br />
<br />
This explains how to install Gtk2Hs-0.10.1 on Mac OS X 10.6 Snow Leopard, in combination with GTK+ from MacPorts.<br />
<br />
* Install the [http://hackage.haskell.org/platform/ Haskell Platform] for Mac<br />
* Download gtk2hs from [http://www.haskell.org/gtk2hs/ Gtk2Hs website] and untar it.<br />
* Install gtk, cairo, etc. from MacPorts like this (note that the <tt>+universal</tt> is needed; if you already installed gtk or one of its dependencies, it is recommended you reinstall those as detailed in the NB at the end of this section).<br />
<pre>sudo port install gtk +universal</pre><br />
* Go to the directory where gtk2hs is untarred and run<br />
<pre>./configure --disable-split-objs --disable-gio<br />
make<br />
sudo make install</pre><br />
<br />
Alternatively, if you wish to follow the Mac OS X style of directory layout, you can use this configure command instead:<br />
<pre>./configure --with-pkgconf=/Users/$USER/.ghc/i386-darwin-6.10.4/package.conf --prefix=/Users/$USER/Library/Haskell/packages/gtk2hs --disable-split-objs --disable-gio</pre><br />
<br />
Right now you should be able to run the demos. Unfortunately, to build any libraries depending on Gtk2Hs, such as [http://hackage.haskell.org/package/Chart/ Chart], you need to edit one more file. You will need to find <tt>package.conf</tt> for your installed GHC by running<br />
<br />
<pre>ghc-pkg list</pre><br />
<br />
In the output you will see the full directory to your <tt>package.conf</tt> file. In this file, you need to search for "gthread", and everywhere you can find it, add <tt>"/opt/local/lib"</tt> (with quotes) to the <tt>libraryDirs</tt> array before it.<br />
<br />
If all went well, it should be properly installed now.<br />
<br />
NB: If compiling fails with architecture errors for certain dynlibs, you need to reinstall the packages these dynlibs belong to with <tt>+universal</tt> by doing<br />
<br />
<pre>sudo port upgrade packagename --enforce-variants +universal</pre><br />
<br />
Alternatively, and this is recommended, you can follow the steps on [http://passingcuriosity.com/2009/haskell-on-snow-leopard/ Haskell On Snow Leopard Blogpost] to immediately add the universal variant of each package:<br />
# Edit <tt>/opt/local/macports/variants.conf</tt> and add <tt>+universal</tt> to the end of this file<br />
# sudo port selfupdate <br />
# sudo port sync<br />
# sudo port upgrade --force installed<br />
<br />
== GTK+ OS X Framework ==<br />
<br />
This explains how to install Gtk2Hs on Macs using the native [http://gtk-osx.sourceforge.net/ GTK+ OS X Framework], a port of GTK+ to the Mac that does '''not''' depend on X11, and hence, is better integrated into the Mac desktop - i.e., menus actually appear in the menu bar, where they belong. It also avoids the often tedious installation of GTK+ via MacPorts. However, it misses support for optional Gtk2Hs packages that are currently not supported by the [http://gtk-osx.sourceforge.net/ GTK+ OS X Framework], most notably support for Glade. It does include support for Cairo, though.<br />
<br />
Here is how to install the library:<br />
# Download and install [http://gtk-osx.sourceforge.net/ GTK+ OS X Framework] (this uses the standard Mac package installer).<br />
# Install [http://pkg-config.freedesktop.org/ pkg-config], either by compiling it from source or via MacPorts.<br />
# Download and unpack the Gtk2Hs tar ball from the [http://www.haskell.org/gtk2hs/download/ Gtk2Hs download page] (I tested 0.10.0).<br />
# Configure with (you may want to remove the two backslashes and put everything on one line)<br />
env PKG_CONFIG_PATH=/Library/Frameworks/Cairo.framework/Resources/dev/lib/pkgconfig:\ <br />
/Library/Frameworks/GLib.framework/Resources/dev/lib/pkgconfig:\ <br />
/Library/Frameworks/Gtk.framework/Resources/dev/lib/pkgconfig ./configure --disable-gio<br />
# Build with<br />
make<br />
# Install (to <tt>/usr/local/</tt> unless a <tt>--prefix</tt> option was passed to <tt>configure</tt>) with<br />
sudo make install<br />
<br />
The library is now registered with the package database of the GHC you used for compiling.<br />
<br />
NB: Thanks to Ross Mellgren for his post on the gtk2hs-users list that outlined the use of <tt>PKG_CONFIG_PATH</tt>.</div>Leoncamelhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/6&diff=4336199 questions/Solutions/62011-12-05T19:30:00Z<p>Leoncamel: </p>
<hr />
<div>(*) Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x).<br />
<br />
<haskell><br />
isPalindrome :: (Eq a) => [a] -> Bool<br />
isPalindrome xs = xs == (reverse xs)<br />
</haskell><br />
<br />
<haskell><br />
isPalindrome' [] = True<br />
isPalindrome' [_] = True<br />
isPalindrome' xs = (head xs) == (last xs) && (isPalindrome' $ init $ tail xs) <br />
</haskell><br />
<br />
Here's one to show it done in a fold just for the fun of it. Do note that it is less efficient then the previous 2 though.<br />
<br />
<haskell><br />
isPalindrome'' :: (Eq a) => [a] -> Bool<br />
isPalindrome'' xs = foldl (\acc (a,b) -> if a == b then acc else False) True input<br />
where<br />
input = zip xs (reverse xs)<br />
</haskell><br />
<br />
Another one just for fun:<br />
<br />
<haskell><br />
isPalindrome''' :: (Eq a) => [a] -> Bool<br />
isPalindrome''' = Control.Monad.liftM2 (==) id reverse<br />
</haskell><br />
<br />
Or even:<br />
<br />
<haskell><br />
isPalindrome'''' :: (Eq a) => [a] -> Bool<br />
isPalindrome'''' = (==) Control.Applicative.<*> reverse<br />
</haskell><br />
<br />
Here's one that does half as many compares:<br />
<br />
<haskell><br />
palindrome :: (Eq a) => [a] -> Bool<br />
palindrome xs = p [] xs xs<br />
where p rev (x:xs) (_:_:ys) = p (x:rev) xs ys<br />
p rev (x:xs) [_] = rev == xs<br />
p rev xs [] = rev == xs<br />
</haskell><br />
<br />
Here's one using foldr and zipWith.<br />
<br />
<haskell><br />
palindrome :: (Eq a) => [a] -> Bool<br />
palindrome xs = foldr (&&) True $ zipWith (==) xs (reverse xs)<br />
</haskell></div>Leoncamelhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/6&diff=4326999 questions/Solutions/62011-11-29T01:52:15Z<p>Leoncamel: </p>
<hr />
<div>(*) Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x).<br />
<br />
<haskell><br />
isPalindrome :: (Eq a) => [a] -> Bool<br />
isPalindrome xs = xs == (reverse xs)<br />
</haskell><br />
<br />
<haskell><br />
isPalindrome' [] = True<br />
isPalindrome' [_] = True<br />
isPalindrome' xs = (head xs) == (last xs) && (isPalindrome' $ init $ tail xs) <br />
</haskell><br />
<br />
Here's one to show it done in a fold just for the fun of it. Do note that it is less efficient then the previous 2 though.<br />
<br />
<haskell><br />
isPalindrome'' :: (Eq a) => [a] -> Bool<br />
isPalindrome'' xs = foldl (\acc (a,b) -> if a == b then acc else False) True input<br />
where<br />
input = zip xs (reverse xs)<br />
</haskell><br />
<br />
Another one just for fun:<br />
<br />
<haskell><br />
isPalindrome''' :: (Eq a) => [a] -> Bool<br />
isPalindrome''' = Control.Monad.liftM2 (==) id reverse<br />
</haskell><br />
<br />
Or even:<br />
<br />
<haskell><br />
isPalindrome'''' :: (Eq a) => [a] -> Bool<br />
ispalindrome'''' = (==) Control.Applicative.<*> reverse<br />
</haskell><br />
<br />
Here's one that does half as many compares:<br />
<br />
<haskell><br />
palindrome :: (Eq a) => [a] -> Bool<br />
palindrome xs = p [] xs xs<br />
where p rev (x:xs) (_:_:ys) = p (x:rev) xs ys<br />
p rev (x:xs) [_] = rev == xs<br />
p rev xs [] = rev == xs<br />
</haskell><br />
<br />
Here's one using foldr and zipWith.<br />
<br />
<haskell><br />
palindrome :: (Eq a) => [a] -> Bool<br />
palindrome xs = foldr (&&) True $ zipWith (==) xs (reverse xs)<br />
</haskell></div>Leoncamelhttps://wiki.haskell.org/index.php?title=Performance&diff=21612Performance2008-07-04T23:42:43Z<p>Leoncamel: Add notation for shell prompt</p>
<hr />
<div>{{Performance infobox}}<br />
Welcome to the '''Haskell Performance Resource''', the collected wisdom on how to make your Haskell programs go faster. <br />
<br />
== Introduction ==<br />
<br />
In most cases it is possible to write a Haskell program that performs as well as, or better than, the same program written in [''insert language here'']. There's a big caveat though: you may have to modify your code significantly in order to improve its performance. Compilers such as GHC are good at eliminating layers of abstraction, but they aren't perfect, and often need some help. <br />
<br />
There are many non-invasive techniques: compiler options, for example. Then there are techniques that require adding some small amounts of performance cruft to your program: strictness annotations, for example. If you still don't get the best performance, though, it might be necessary to resort to larger refactorings.<br />
<br />
Sometimes the code tweaks required to get the best performance are non-portable, perhaps because they require language extensions that aren't implemented in all compilers (e.g. unboxing), or because they require using platform-specific features or libraries. This might not be acceptable in your setting.<br />
<br />
If the worst comes to the worst, you can always write your critical code in C and use the FFI to call it. Beware of the boundaries though - marshaling data across the FFI can be expensive, and multi-language memory management can be complex and error-prone. It's usually better to stick to Haskell if possible.<br />
<br />
== Basic techniques ==<br />
<br />
The key tool to use in making your Haskell program run faster is ''profiling''. Profiling is provided by [[GHC]] and [[nhc98]]. There is ''no substitute'' for finding where your program's time/space is ''really'' going, as opposed to where you imagine it is going.<br />
<br />
Another point to bear in mind: By far the best way to improve a program's performance ''dramatically'' is to use better algorithms. Once profiling has thrown the spotlight on the guilty time-consumer(s), it may be better to re-think your program than to try all the tweaks listed below.<br />
<br />
Another extremely efficient way to make your program snappy is to use library code that has been Seriously Tuned By Someone Else. You ''might'' be able to write a better sorting function than the one in <tt>Data.List</tt>, but it will take you much longer than typing <tt>import Data.List</tt>.<br />
<br />
We have chosen to organise the rest of this resource first by Haskell construct (data types, pattern matching, integers), and then within each category to describe techniques that apply across implementations, and also techniques that are specific to a certain Haskell implementation (e.g. GHC). There are some implementation-specific techniques that apply in general - those are linked from the [[Haskell Performance Resource#General_Implementation-Specific_Techniques | General Implementation-Specific Techniques]] section below.<br />
<br />
== Haskell constructs ==<br />
<br />
* [[/Data Types/]]<br />
* [[/Functions/]]<br />
* [[/Overloading/]]<br />
* [[/FFI/]]<br />
* [[/Arrays/]]<br />
* [[/Strings/]]<br />
* [[/Integers/]]<br />
* [[/IO | I/O ]]<br />
* [[/Floating Point/]]<br />
* [[/Concurrency/]]<br />
* [[/Modules/]]<br />
* [[/Monads/]]<br />
<br />
== General techniques ==<br />
<br />
* [[/Strictness/]]<br />
* [[/Laziness/]]<br />
* [[/Space | Avoiding space leaks]]<br />
* [[/Accumulating parameter|Accumulating parameters]]<br />
* [[Stack_overflow|Avoiding stack overflow]]<br />
<br />
== Compiler specific techniques ==<br />
<br />
* [[/GHC/]]<br />
* [[/NHC98| nhc98]]<br />
* [[/Hugs/]]<br />
* [[/Yhc/]]<br />
* [[/JHC/]]<br />
<br />
== More information ==<br />
<br />
* There are plenty of good examples of Haskell code written for performance in the [http://shootout.alioth.debian.org/ The Computer Language Shootout Benchmarks]<br />
* And many alternatives, with discussion, on the [http://web.archive.org/web/20060209215702/http://haskell.org/hawiki/ShootoutEntry old Haskell wiki]<br />
<br />
== Specific comparisons of data structures ==<br />
=== Data.Sequence vs. lists ===<br />
<br />
Data.Sequence has complexity O(log(min(i,n-i))) for access, insertion and update to position i of a sequence of length n.<br />
<br />
List has complexity O(i).<br />
<br />
List is a non-trivial constant-factor faster for operations at the head (cons and head), making it a more efficient choice for stack-like and stream-like access patterns. Data.Sequence is faster for every other access pattern, such as queue and random access.<br />
<br />
See the following program for proof:<br />
<haskell><br />
import Data.Sequence<br />
<br />
insert_million 0 sequence = sequence<br />
insert_million n sequence = insert_million (n - 1)(sequence |> n)<br />
<br />
main = putStrLn (show (Data.Sequence.length (insert_million 1000000 empty)))<br />
</haskell><br />
<pre><br />
$ ghc -O2 --make InsertMillionElements.hs && time ./InsertMillionElements +RTS -K100M<br />
1000000<br />
real 0m7.238s<br />
user 0m6.804s<br />
sys 0m0.228s<br />
</pre><br />
<haskell><br />
insert_million 0 list = reverse list<br />
insert_million n list = insert_million (n -1) (n:list)<br />
<br />
main = putStrLn (show (length (insert_million 1000000 [])))<br />
</haskell><br />
<pre><br />
$ ghc -O2 --make InsertMillionElements.hs && time ./InsertMillionElementsList +RTS -K100M<br />
1000000<br />
real 0m0.588s<br />
user 0m0.528s<br />
sys 0m0.052s<br />
</pre><br />
Lists are substantially faster on this micro-benchmark.<br />
<br />
A sequence uses between 5/6 and 4/3 times as much space as the equivalent list (assuming an overhead of one word per node, as in GHC).<br />
If only deque operations are used, the space usage will be near the lower end of the range, because all internal nodes will be ternary.<br />
Heavy use of split and append will result in sequences using approximately the same space as lists.<br />
In detail:<br />
* a list of length ''n'' consists of ''n'' cons nodes, each occupying 3 words.<br />
* a sequence of length ''n'' has approximately ''n''/(''k''-1) nodes, where ''k'' is the average arity of the internal nodes (each 2 or 3). There is a pointer, a size and overhead for each node, plus a pointer for each element, i.e. ''n''(3/(''k''-1) + 1) words.<br />
<br />
== Additional Tips ==<br />
<br />
* Use strict returns ( return $! ...) unless you absolutely need them lazy.<br />
* foldl' over foldr unless you have to use foldr.<br />
* Profile, profile, profile - understand who is hanging on to the memory (+RTS -hc) and how it's being used (+RTS -hb).<br />
* Use +RTS -p to understand who's doing all the allocations and where your time is being spent.<br />
* Approach profiling like a science experiment - make one change, observe if anything is different, rollback and make another change - observer the change. Keep notes!<br />
<br />
<br />
[[Category:Idioms]]<br />
[[Category:Language]]<br />
[[Category:Performance|*]]</div>Leoncamelhttps://wiki.haskell.org/index.php?title=99_questions/31_to_41&diff=2159799 questions/31 to 412008-07-04T04:10:55Z<p>Leoncamel: </p>
<hr />
<div>__NOTOC__<br />
<br />
This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ Ninety-Nine Prolog Problems].<br />
<br />
== Arithmetic ==<br />
<br />
== Problem 31 ==<br />
<br />
(**) Determine whether a given integer number is prime.<br />
<br />
Example:<br />
<pre><br />
* (is-prime 7)<br />
T<br />
</pre><br />
Example in Haskell:<br />
<pre><br />
P31> isPrime 7<br />
True<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
isPrime :: Integral a => a -> Bool<br />
isPrime p = p > 1 && (all (\n -> p `mod` n /= 0 ) $ takeWhile (\n -> n*n <= p) [2..])<br />
</haskell><br />
<br />
Well, a natural number p is a prime number iff it is larger than 1 and no natural number n with n >= 2 and n^2 <= p is a divisor of p. That's exactly what is implemented: we take the list of all integral numbers starting with 2 as long as their square is at most p and check that for all these n there is a remainder concerning the division of p by n.<br />
<br />
== Problem 32 ==<br />
<br />
(**) Determine the greatest common divisor of two positive integer numbers.<br />
Use Euclid's algorithm.<br />
<br />
<pre><br />
Example:<br />
* (gcd 36 63)<br />
9<br />
<br />
Example in Haskell:<br />
[myGCD 36 63, myGCD (-3) (-6), myGCD (-3) 6]<br />
[9,3,3]<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
gcd' 0 y = y<br />
gcd' x y = gcd' (y `mod` x) x<br />
myGCD x y | x < 0 = myGCD (-x) y<br />
| y < 0 = myGCD x (-y)<br />
| y < x = gcd' y x<br />
| otherwise = gcd' x y<br />
</haskell><br />
<br />
The Prelude includes a gcd function, so we have to choose another name for ours. The function gcd' is a straightforward implementation of Euler's algorithm, and myGCD is just a wrapper that makes sure the arguments are positive and in increasing order.<br />
<br />
A more concise implementation is:<br />
<haskell><br />
myGCD :: Integer -> Integer -> Integer<br />
myGCD a b<br />
| b == 0 = abs a<br />
| otherwise = myGCD b (a `mod` b)<br />
</haskell><br />
<br />
== Problem 33 ==<br />
<br />
(*) Determine whether two positive integer numbers are coprime.<br />
Two numbers are coprime if their greatest common divisor equals 1.<br />
<br />
Example:<br />
<pre><br />
* (coprime 35 64)<br />
T<br />
</pre><br />
<br />
Example in Haskell:<br />
<pre><br />
* coprime 35 64<br />
True <br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
coprime a b = gcd a b == 1<br />
</haskell><br />
<br />
Here we use the prelude function for computing gcd's along with a test of the result's equality to one. <br />
<br />
== Problem 34 ==<br />
<br />
(**) Calculate Euler's totient function phi(m).<br />
Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.<br />
Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.<br />
<pre><br />
Example:<br />
* (totient-phi 10)<br />
4<br />
Example in Haskell:<br />
* totient 10<br />
4<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
totient 1 = 1<br />
totient a = length $ filter (coprime a) [1..a-1]<br />
where coprime a b = gcd a b == 1<br />
</haskell><br />
<br />
We take coprime from the previous exercise and give it to filter, which applies it to each element of a list from 1 to one less than the number, returning only those that are true. length tells us how many elements are in the resulting list, and thus how many elements are coprime to n<br />
<br />
== Problem 35 ==<br />
<br />
(**) Determine the prime factors of a given positive integer.<br />
Construct a flat list containing the prime factors in ascending order.<br />
<br />
Example:<br />
<pre><br />
* (prime-factors 315)<br />
(3 3 5 7)<br />
</pre><br />
Example in Haskell:<br />
<pre><br />
> primeFactors 315<br />
[3, 3, 5, 7]<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
primeFactors :: Integer -> [Integer]<br />
primeFactors a = let (f, f1) = factorPairOf a<br />
f' = if prime f then [f] else primeFactors f<br />
f1' = if prime f1 then [f1] else primeFactors f1<br />
in f' ++ f1'<br />
where<br />
factorPairOf a = let f = head $ factors a<br />
in (f, div a f)<br />
factors a = filter (isFactor a) [2..a-1]<br />
isFactor a b = rem a b == 0<br />
prime a = (length $ factors a) == 0<br />
</haskell><br />
<br />
Kind of ugly, but it works, though it may have bugs in corner cases. This uses the factor tree method of finding prime factors of a number. factorPairOf picks a factor and takes it and the factor you multiply it by and gives them to primeFactors. primeFactors checks to make sure the factors are prime. If not it prime factorizes them. In the end a list of prime factors is returned.<br />
<br />
Another possibility is to observe that you need not ensure that potential divisors are primes, as long as you consider them in ascending order:<br />
<haskell><br />
primeFactors n = primeFactors' n 2 where<br />
primeFactors' 1 _ = []<br />
primeFactors' n factor<br />
| n `mod` factor == 0 = factor : primeFactors' (n `div` factor) factor<br />
| otherwise = primeFactors' n (factor + 1)<br />
</haskell><br />
Thus, we just loop through all possible factors and add them to the list if they divide the original number. As the primes get farther apart, though, this will do a lot of needless checks to see if composite numbers are prime factors.<br />
However we can stop as soon as the candidate factor exceeds the square root of n:<br />
<haskell><br />
primeFactors n = primeFactors' n 2 where<br />
primeFactors' n factor<br />
| factor*factor > n = [n]<br />
| n `mod` factor == 0 = factor : primeFactors' (n `div` factor) factor<br />
| otherwise = primeFactors' n (factor + 1)<br />
</haskell><br />
<br />
You can avoid the needless work by just looping through the primes:<br />
<haskell><br />
primeFactors n = factor n primes<br />
where factor n (p:ps) | p*p > n = [n]<br />
| n `mod` p /= 0 = factor n ps<br />
| otherwise = p : factor (n `div` p) (p:ps)<br />
primes = 2 : filter ((==1) . length . primeFactors) [3,5..]<br />
</haskell><br />
(see also discussion of this solution following "Discuss this page")<br />
<br />
== Problem 36 ==<br />
(**) Determine the prime factors of a given positive integer.<br />
<br />
Construct a list containing the prime factors and their multiplicity.<br />
<br />
Example:<br />
<pre><br />
* (prime-factors-mult 315)<br />
((3 2) (5 1) (7 1))<br />
</pre><br />
Example in Haskell:<br />
<pre><br />
*Main> prime_factors_mult 315<br />
[(3,2),(5,1),(7,1)]<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
prime_factors_mult n = map swap $ encode $ primeFactors n<br />
where swap (x,y) = (y,x)<br />
</haskell><br />
using <tt>primeFactors</tt> from problem 35 to generate the list of prime factors in ascending order, and <tt>encode</tt> from problem 10 to compress this list to a list of numbers paired with their multiplicity.<br />
<br />
== Problem 37 ==<br />
<br />
(**) Calculate Euler's totient function phi(m) (improved).<br />
See problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem 36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:<br />
<br />
<pre><br />
phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...<br />
</pre><br />
<br />
Note that a ** b stands for the b'th power of a.<br />
<i>Note</i>: Actually, the official problems show this as a sum, but it should be a product.<br />
<br />
Solution: Given prime_factors_mult from problem 36, we get<br />
<haskell><br />
totient m = product [(p - 1) * p ^ (c - 1) | (p, c) <- prime_factors_mult m]<br />
</haskell><br />
This just uses a list comprehension to build each term of the product in the formula for phi, then multiplies them all.<br />
<br />
== Problem 38 ==<br />
<br />
(*) Compare the two methods of calculating Euler's totient function.<br />
<br />
Use the solutions of problems 34 and 37 to compare the algorithms. Take the number of reductions as a measure for efficiency. Try to calculate phi(10090) as an example.<br />
<br />
(no solution required)<br />
<br />
== Problem 39 ==<br />
<br />
(*) A list of prime numbers.<br />
<br />
Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.<br />
<br />
<pre><br />
Example in Haskell:<br />
P29> primesR 10 20<br />
[11,13,17,19]<br />
</pre><br />
<br />
Solution 1:<br />
<haskell><br />
primesR :: Integral a => a -> a -> [a]<br />
primesR a b = filter isPrime [a..b]<br />
</haskell><br />
<br />
If we are challenged to give all primes in the range between a and b we simply take all number from a up to b and filter the primes out.<br />
<br />
Solution 2:<br />
<haskell><br />
primes :: Integral a => [a]<br />
primes = let sieve (n:ns) = n:sieve [ m | m <- ns, m `mod` n /= 0 ] in sieve [2..]<br />
<br />
primesR :: Integral a => a -> a -> [a]<br />
primesR a b = takeWhile (<= b) $ dropWhile (< a) primes<br />
</haskell><br />
<br />
Another way to compute the claimed list is done by using the ''Sieve of Eratosthenes''. The <hask>primes</hask> function generates a list of all (!) prime numbers using this algorithm and <hask>primesR</hask> filter the relevant range out. [But this way is very slow and I only presented it because I wanted to show how nice the ''Sieve of Eratosthenes'' can be implemented in Haskell :)]<br />
<br />
== Problem 40 ==<br />
(**) Goldbach's conjecture.<br />
Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer.<br />
<br />
<pre><br />
Example:<br />
* (goldbach 28)<br />
(5 23)<br />
<br />
Example in Haskell:<br />
*goldbach 28<br />
(5, 23)<br />
</pre><br />
<br />
Solution 1:<br />
<haskell><br />
goldbach a = head $<br />
filter (\e -> (isPrime $ fst e) && (isPrime $ snd e)) $<br />
map (\e -> (e, a - e)) [1,3..div a 2]<br />
where<br />
factors a = filter (isFactor a) [2..a-1]<br />
isFactor a b = rem a b == 0<br />
isPrime a = (length $ factors a) == 0<br />
</haskell><br />
<br />
Woohoo! I've solved the goldbach conjecture! Where do I collect my prize? This does the obvious thing. It makes a list of odd numbers and then uses it to make up pairs of odd numbers that sum to n. Then it looks for a pair of odd numbers where both are prime and returns it as a tuple.<br />
<br />
Solution 2:<br />
<haskell><br />
-- using the previous problem...<br />
goldbach n = head [(x,y) | x <- pr, y <- pr, x+y==n]<br />
where pr = takeWhile (< n) primes<br />
</haskell><br />
<br />
Solution 3:<br />
<haskell><br />
goldbach n = head [(x,y) | x <- takeWhile (< n) primes, let y = n-x, isPrime y]<br />
</haskell><br />
<br />
== Problem 41 ==<br />
<br />
(**) Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.<br />
<br />
In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50. Try to find out how many such cases there are in the range 2..3000.<br />
<br />
Example:<br />
<pre><br />
* (goldbach-list 9 20)<br />
10 = 3 + 7<br />
12 = 5 + 7<br />
14 = 3 + 11<br />
16 = 3 + 13<br />
18 = 5 + 13<br />
20 = 3 + 17<br />
* (goldbach-list 1 2000 50)<br />
992 = 73 + 919<br />
1382 = 61 + 1321<br />
1856 = 67 + 1789<br />
1928 = 61 + 1867<br />
</pre><br />
<br />
Example in Haskell:<br />
<pre><br />
*Exercises> goldbachList 9 20<br />
[(3,7),(5,7),(3,11),(3,13),(5,13),(3,17)]<br />
*Exercises> goldbachList' 4 2000 50<br />
[(73,919),(61,1321),(67,1789),(61,1867)]<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
goldbachList lb ub = map goldbach $ [even_lb,even_lb+2..ub]<br />
where even_lb = max ((lb+1) `div` 2 * 2) 4<br />
goldbachList' lb ub mv = filter (\(a,b) -> a > mv && b > mv) $<br />
goldbachList lb ub<br />
</haskell><br />
using the <tt>goldbach</tt> function from problem 40.<br />
<br />
[[Category:Tutorials]]</div>Leoncamel