https://wiki.haskell.org/api.php?action=feedcontributions&user=Drbb&feedformat=atomHaskellWiki - User contributions [en]2020-10-26T08:48:38ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Monad/ST&diff=47108Monad/ST2012-07-24T15:48:37Z<p>Drbb: remove chatter</p>
<hr />
<div>{{Standard class|ST|module=Control.Monad.ST|module-doc=Control-Monad-ST|package=base}}<br />
<br />
The ST monad provides support for ''strict'' state threads.<br />
<br />
<br />
==A discussion on the Haskell irc ==<br />
From #haskell (see 13:05:37 in the [http://tunes.org/~nef/logs/haskell/07.02.07 log] ):<br />
<br />
* TuringTest: ST lets you implement algorithms that are much more efficient with mutable memory used internally. But the whole "thread" of computation cannot exchange mutable state with the outside world, it can only exchange immutable state.<br />
<br />
* TuringTest: chessguy: You pass in normal Haskell values and then use ST to allocate mutable memory, then you initialize and play with it, then you put it away and return a normal Haskell value.<br />
<br />
* sjanssen: a monad that has mutable references and arrays, but has a "run" function that is referentially transparent<br />
<br />
* DapperDan2: it strikes me that ST is like a lexical scope, where all the variables/state disappear when the function returns.<br />
[[Category:Standard classes]] [[Category:Monad]]<br />
<br />
<br />
==An explanation in Haskell-Cafe==<br />
<br />
The ST monad lets you use update-in-place, but is escapable (unlike IO). <br />
ST actions have the form:<br />
<br />
<haskell><br />
ST s α<br />
</haskell><br />
<br />
Meaning that they return a value of type α, and execute in "thread" s.<br />
All reference types are tagged with the thread, so that actions can only<br />
affect references in their own "thread".<br />
<br />
Now, the type of the function used to escape ST is:<br />
<br />
<haskell><br />
runST :: forall α. (forall s. ST s α) -> α<br />
</haskell><br />
<br />
The action you pass must be universal in s, so inside your action you don't know what thread, thus you cannot access any other threads, thus <hask>runST</hask> is pure. This is very useful, since it allows you to implement externally pure things like in-place quicksort, and present them as pure functions ∀ e. Ord e ⇒ Array e → Array e; without using any unsafe functions.<br />
<br />
But that type of <hask>runST</hask> is illegal in Haskell-98, because it needs a universal quantifier *inside* the function-arrow! In the jargon, that type has rank 2; haskell 98 types may have rank at most 1.<br />
<br />
See http://www.haskell.org/pipermail/haskell-cafe/2007-July/028233.html<br />
<br />
== A few simple examples ==<br />
<br />
In this example, we define a version of the function sum, but do it in a way which more like how it would be done in imperative languages, where a variable is updated, rather than a new value is formed and passed to the next iteration of the function. While in place modifications of the STRef n are occurring, something that would usually be considered a side effect, it is all done in a safe way which is deterministic. The result is that we get the benefits of being able to modify memory in place, while still producing a pure function with the use of runST.<br />
<br />
<haskell><br />
import Control.Monad.ST<br />
import Data.STRef<br />
import Control.Monad<br />
<br />
<br />
sumST :: Num a => [a] -> a<br />
sumST xs = runST $ do -- runST takes out stateful code and makes it pure again.<br />
<br />
n <- newSTRef 0 -- Create an STRef (place in memory to store values)<br />
<br />
forM_ xs $ \x -> do -- For each element of xs ..<br />
modifySTRef n (+x) -- add it to what we have in n.<br />
<br />
readSTRef n -- read the value of n, and return it.<br />
<br />
<br />
</haskell><br />
<br />
An implementation of foldl using the ST monad (a lot like sum, and in fact sum can be defined in terms of foldlST):<br />
<br />
<haskell><br />
foldlST :: (a -> b -> a) -> a -> [b] -> a<br />
foldlST f acc xs = runST $ do<br />
acc' <- newSTRef acc -- Create a variable for the accumulator<br />
<br />
forM_ xs $ \x -> do -- For each x in xs...<br />
<br />
a <- readSTRef acc' -- read the accumulator<br />
writeSTRef acc' (f a x) -- apply f to the accumulator and x<br />
<br />
readSTRef acc' -- and finally read the result<br />
</haskell><br />
<br />
An example of the Fibonacci function running in constant¹ space:<br />
<br />
<haskell><br />
fibST :: Integer -> Integer<br />
fibST n = <br />
if n < 2<br />
then n<br />
else runST $ do<br />
x <- newSTRef 0<br />
y <- newSTRef 1<br />
fibST' n x y<br />
<br />
where fibST' 0 x _ = readSTRef x<br />
fibST' n x y = do<br />
x' <- readSTRef x<br />
y' <- readSTRef y<br />
writeSTRef x y'<br />
writeSTRef y $! x'+y'<br />
fibST' (n-1) x y<br />
</haskell><br />
<br />
[1] Since we're using Integers, technically it's not constant space, as they grow in size when they get bigger, but we can ignore this.<br />
<br />
== References ==<br />
* [http://research.microsoft.com/en-us/um/people/simonpj/papers/lazy-functional-state-threads.ps.Z Lazy Functional State Threads, John Launchbury and Simon Peyton Jones]<br />
* [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad-ST.html Control.Monad.ST in the base libraries]</div>Drbbhttps://wiki.haskell.org/index.php?title=Talk:GHC.Generics&diff=44724Talk:GHC.Generics2012-03-03T04:45:54Z<p>Drbb: </p>
<hr />
<div>Why does the definition of (:+:) use the pipe character "|", but the definition of (:*:) uses the ":*:" operator?<br />
<br />
<br />
Is that a typo (copied from http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/generic-programming.html), or is there a reason for the difference?<br />
<br />
-- | Sums: encode choice between constructors<br />
infixr 5 :+:<br />
data (:+:) f g p = L1 (f p) | R1 (g p)<br />
<br />
-- | Products: encode multiple arguments to constructors<br />
infixr 6 :*:<br />
data (:*:) f g p = f p :*: g p<br />
<br />
<br />
Is it just fallout from of "asymmetry" in Haskell language spec, <br />
where Sum types need the pipe to separate the alternations, <br />
but Product types are written with the factors simply adjacent without a separator? (and then it looks pretty to use infix constructor ":*:" instead of a prefix constructor "P")</div>Drbbhttps://wiki.haskell.org/index.php?title=Talk:GHC.Generics&diff=44723Talk:GHC.Generics2012-03-03T04:00:49Z<p>Drbb: </p>
<hr />
<div>Why does the definition of (:+:) use the pipe character "|", but the definition of (:*:) uses the ":*:" operator?<br />
<br />
<br />
Is that a typo (copied from http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/generic-programming.html), or is there a reason for the difference?<br />
<br />
-- | Sums: encode choice between constructors<br />
infixr 5 :+:<br />
data (:+:) f g p = L1 (f p) | R1 (g p)<br />
<br />
-- | Products: encode multiple arguments to constructors<br />
infixr 6 :*:<br />
data (:*:) f g p = f p :*: g p</div>Drbbhttps://wiki.haskell.org/index.php?title=Talk:GHC.Generics&diff=44722Talk:GHC.Generics2012-03-03T04:00:36Z<p>Drbb: typo?</p>
<hr />
<div>Why does the definition of (:+:) use the pipe character "|", but the definition of (:*:) uses the ":*:" operator?<br />
<br />
<br />
Is that a typo (copied from http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/generic-programming.html, or is there a reason for the difference?<br />
<br />
-- | Sums: encode choice between constructors<br />
infixr 5 :+:<br />
data (:+:) f g p = L1 (f p) | R1 (g p)<br />
<br />
-- | Products: encode multiple arguments to constructors<br />
infixr 6 :*:<br />
data (:*:) f g p = f p :*: g p</div>Drbbhttps://wiki.haskell.org/index.php?title=Arrays&diff=44171Arrays2012-01-23T23:47:47Z<p>Drbb: /* DiffArray (module Data.Array.Diff) */</p>
<hr />
<div>Haskell'98 supports just one array constructor type, namely [http://haskell.org/onlinereport/array.html Array], which gives you immutable<br />
boxed arrays. "Immutable" means that these arrays, like any other pure<br />
functional data structure, have contents fixed at construction time.<br />
You can't modify them, only query. There are "modification" operations,<br />
but they just return new arrays and don't modify the original one. This<br />
makes it possible to use Arrays in pure functional code along with lists.<br />
"Boxed" means that array elements are just ordinary Haskell (lazy)<br />
values, which are evaluated on demand, and can even contain bottom<br />
(undefined) values. You can learn how to use these arrays at<br />
http://haskell.org/tutorial/arrays.html and I'd recommend that you read<br />
this before proceeding to the rest of this page<br />
<br />
Nowadays the main Haskell compilers, GHC and Hugs, ship with<br />
the same set of [http://www.haskell.org/ghc/docs/latest/html/libraries/index.html Hierarchical Libraries],<br />
and these libraries contain a new implementation of arrays which is<br />
backward compatible with the Haskell'98 one, but which has far more features.<br />
Suffice it to say that these libraries support 9 types of array<br />
constructors: Array, UArray, IOArray, IOUArray, STArray, STUArray,<br />
DiffArray, DiffUArray and StorableArray. Each provides just one of two interfaces, and one of these you already know.<br />
<br />
== Quick reference ==<br />
<br />
{| class="wikitable" style="text-align:center;"<br />
!<br />
! Immutable<br><hask>instance IArray a e</hask><br />
! IO monad<br><hask>instance MArray a e IO</hask><br />
! ST monad<br><hask>instance MArray a e ST</hask><br />
|-<br />
! Standard<br />
| <hask>Array</hask><br><hask>DiffArray</hask><br />
| <hask>IOArray</hask><br />
| <hask>STArray</hask><br />
|-<br />
! Unboxed<br />
| <hask>UArray</hask><br><hask>DiffUArray</hask><br />
| <hask>IOUArray</hask><br><hask>StorableArray</hask><br />
| <hask>STUArray</hask><br />
|}<br />
<br />
== Immutable arrays (module [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-IArray.html Data.Array.IArray]) ==<br />
<br />
The first interface provided by the new array library, is defined<br />
by the typeclass IArray (which stands for "immutable array" and defined<br />
in the module [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-IArray.html Data.Array.IArray])<br />
and defines the same operations that were defined for Array in<br />
Haskell'98. The big difference is that it is now a typeclass and there are 4<br />
array type constructors, each of which implements this interface: Array,<br />
UArray, DiffArray, and DiffUArray. We will later describe the differences<br />
between them and the cases when these other types are preferable to use instead<br />
of the good old Array. Also note that to use Array type constructor<br />
together with other new array types, you need to import<br />
Data.Array.IArray module instead of Data.Array<br />
<br />
<br />
<br />
== Mutable IO arrays (module [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-IO.html Data.Array.IO]) ==<br />
<br />
The second interface is defined by the type class MArray (which stands for<br />
"mutable array" and is defined in the module [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-MArray.html Data.Array.MArray])<br />
and contains operations to update array elements in-place. Mutable<br />
arrays are very similar to IORefs, only they contain multiple values. Type<br />
constructors for mutable arrays are IOArray and IOUArray and<br />
operations which create, update and query these arrays all belong to the<br />
IO monad:<br />
<br />
<haskell><br />
import Data.Array.IO<br />
main = do arr <- newArray (1,10) 37 :: IO (IOArray Int Int)<br />
a <- readArray arr 1<br />
writeArray arr 1 64<br />
b <- readArray arr 1 <br />
print (a,b)<br />
</haskell><br />
<br />
This program creates an array of 10 elements with all values initially set to 37. Then it reads <br />
the first element of the array. After that, the<br />
program modifies the first element of the array and then reads it<br />
again. The type declaration in the second line is necessary because our little<br />
program doesn't provide enough context to allow the compiler to determine the concrete type of `arr`. Unlike examples, real programs rarely need such declarations.<br />
<br />
<br />
<br />
== Mutable arrays in ST monad (module [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-ST.html Data.Array.ST]) ==<br />
<br />
In the same way that IORef has its more general cousin STRef, IOArray has a more<br />
general version STArray (and similarly, IOUArray corresponds to STUArray). These<br />
array types allow one to work with mutable arrays in the ST monad:<br />
<br />
<haskell><br />
import Control.Monad.ST<br />
import Data.Array.ST<br />
<br />
buildPair = do arr <- newArray (1,10) 37 :: ST s (STArray s Int Int)<br />
a <- readArray arr 1<br />
writeArray arr 1 64<br />
b <- readArray arr 1<br />
return (a,b)<br />
<br />
main = print $ runST buildPair<br />
</haskell><br />
<br />
Believe it or not, now you know all that is needed to '''use''' any<br />
array type. Unless you are interested in speed issues, just use Array,<br />
IOArray and STArray where appropriate. The following topics are almost<br />
exclusively about selecting the proper array type to make programs run<br />
faster.<br />
<br />
<br />
<br />
== DiffArray (module [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-Diff.html Data.Array.Diff]) ==<br />
<br />
Note, as of Jan 2012, DiffArray is not yet ready for production use; it's practical (wall clock) performance does not live up to its theoretical advantages.<br />
<br />
As we already stated, the update operation on immutable arrays (IArray)<br />
just creates a new copy of the array, which is very inefficient, but it is a<br />
pure operation which can be used in pure functions. On the other hand,<br />
updates on mutable arrays (MArray) are efficient but can be done only<br />
in monadic code. In theory, DiffArray combines the best of both worlds - it<br />
supports the IArray interface and therefore can be used in a purely<br />
functional way, but internally it uses the efficient update of MArrays.<br />
<br />
(In practice, however, DiffArrays are 10-100x slower than MArrays, due to the overhead of maintaining an immmutable interface. See bug report here: [http://trac.haskell.org/diffarray/ticket/2])<br />
<br />
How does this trick work? DiffArray has a pure external interface, but<br />
internally it is represented as a reference to an IOArray.<br />
<br />
When the '//' operator is applied to a diff array, its contents<br />
are physically updated in place. The old array silently changes<br />
its representation without changing the visible behavior: <br />
it stores a link to the new current array along with the <br />
difference to be applied to get the old contents. <br />
<br />
So if a diff array is used in a single-threaded style, <br />
that is, after '//' application the old version is no longer used, <br />
a!i takes O(1) time and a//d takes O(length d). <br />
Accessing elements of older versions gradually becomes slower. <br />
<br />
Updating an array which is not current makes a physical copy. <br />
The resulting array is unlinked from the old family. So you <br />
can obtain a version which is guaranteed to be current and <br />
thus has fast element access by a//[]. <br />
<br />
The library provides two "differential" array constructors - DiffArray,<br />
made internally from IOArray, and DiffUArray, based on IOUArray. If you really need to, you can construct new "differential" array types from any<br />
'MArray' types living in the 'IO' monad. Since GHC-6.12, DiffArray has been splitted off into separated package due to its "unusably slow". See [http://hackage.haskell.org/package/diffarray Hackage documentation] for further details.<br />
<br />
Usage of DiffArray doesn't differ from that of Array, the only difference is memory consumption and speed:<br />
<br />
<haskell><br />
import Data.Array.Diff<br />
<br />
main = do<br />
let arr = listArray (1,1000) [1..1000] :: DiffArray Int Int<br />
a = arr ! 1<br />
arr2 = arr // [(1,37)]<br />
b = arr2 ! 1<br />
print (a,b)<br />
</haskell><br />
<br />
You can use 'seq' to force evaluation of array elements prior to updating an array:<br />
<br />
<haskell><br />
import Data.Array.Diff<br />
<br />
main = do<br />
let arr = listArray (1,1000) [1..1000] :: DiffArray Int Int<br />
a = arr ! 1<br />
b = arr ! 2<br />
arr2 = a `seq` b `seq` (arr // [(1,37),(2,64)])<br />
c = arr2 ! 1<br />
print (a,b,c)<br />
</haskell><br />
<br />
== Unboxed arrays ==<br />
<br />
In most implementations of lazy evaluation, values are represented at runtime as pointers to either their value, or code for computing their value. This extra level of indirection, together with any extra tags needed by the runtime, is known as a box. The default "boxed" arrays consist of many of these boxes, each of which may compute its value separately. This allows for many neat tricks, like recursively defining an array's elements in terms of one another, or only computing the specific elements of the array which are ever needed. However, for large arrays, it costs a lot in terms of overhead, and if the entire array is always needed, it can be a waste.<br />
<br />
Unboxed arrays are more like arrays in C - they contain just the plain<br />
values without this extra level of indirection, so that, for example,<br />
an array of 1024 values of type Int32 will use only 4 kb of memory. <br />
Moreover, indexing of such arrays can be significantly faster.<br />
<br />
Of course, unboxed arrays have their own disadvantages. First, unboxed<br />
arrays can be made only of plain values having a fixed size - Int, Word,<br />
Char, Bool, Ptr, Double, etc. (see the full list in the [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-Unboxed.html Data.Array.Unboxed] module).<br />
You can even implement unboxed arrays yourself for other<br />
simple types, including enumerations. But Integer, String and any<br />
other types defined with variable size cannot be elements of unboxed arrays.<br />
Second, without that extra level of indirection, all of the elements in an unboxed array must be evaluated when the array is evaluated, so you lose the benefits of lazy evaluation. Indexing the array to read just one element will construct the entire array. This is not much of a loss if you will eventually need the whole array, but it does prevent recursively defining the array elements in terms of each other, and may be too expensive if you only ever need specific values. Nevertheless, unboxed arrays are a very useful optimization<br />
instrument, and I recommend using them as much as possible.<br />
<br />
All main array types in the library have unboxed counterparts:<br />
<br />
Array - UArray (module Data.Array.Unboxed)<br />
IOArray - IOUArray (module Data.Array.IO)<br />
STArray - STUArray (module Data.Array.ST)<br />
DiffArray - DiffUArray (module Data.Array.Diff)<br />
<br />
So, basically replacing boxed arrays in your program with unboxed ones<br />
is very simple - just add 'U' to the type signatures, and you are done! Of course, if you change Array to UArray, you also need to add "Data.Array.Unboxed"<br />
to your imports list.<br />
<br />
<br />
<br />
== StorableArray (module [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-Storable.html Data.Array.Storable]) ==<br />
<br />
A storable array is an IO-mutable array which stores its<br />
contents in a contiguous memory block living in the C<br />
heap. Elements are stored according to the class 'Storable'.<br />
You can obtain the pointer to the array contents to manipulate<br />
elements from languages like C.<br />
<br />
It is similar to 'IOUArray' (in particular, it implements the same<br />
MArray interface) but slower. The advantage is that it's compatible<br />
with C through the foreign function interface. The memory addresses of<br />
storable arrays are fixed, so you can pass them to C routines.<br />
<br />
The pointer to the array contents is obtained by 'withStorableArray'.<br />
The idea is similar to 'ForeignPtr' (used internally here).<br />
The pointer should be used only during execution of the 'IO' action<br />
returned by the function passed as argument to 'withStorableArray'.<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
import Data.Array.Storable<br />
import Foreign.Ptr<br />
import Foreign.C.Types<br />
<br />
main = do arr <- newArray (1,10) 37 :: IO (StorableArray Int Int)<br />
a <- readArray arr 1<br />
withStorableArray arr <br />
(\ptr -> memset ptr 0 40)<br />
b <- readArray arr 1<br />
print (a,b)<br />
<br />
foreign import ccall unsafe "string.h" <br />
memset :: Ptr a -> CInt -> CSize -> IO ()<br />
</haskell><br />
<br />
If you want to use this pointer afterwards, ensure that you call<br />
'touchStorableArray' AFTER the last use of the pointer,<br />
so that the array will be not freed too early.<br />
<br />
<br />
Additional comments: GHC 6.6 made access to <br />
'StorableArray' as fast as to any other unboxed arrays. The only difference between 'StorableArray' and 'UArray' is that UArray lies in relocatable part of GHC heap while 'StorableArray' lies in non-relocatable part and therefore keep the fixed address, what allow to pass this address to the C routines and save it in the C data structures.<br />
<br />
GHC 6.6 also adds an 'unsafeForeignPtrToStorableArray' operation that allows<br />
the use of any Ptr as the address of a 'StorableArray' and in particular works with<br />
arrays returned by C routines. Here is an example of using this operation:<br />
<br />
<haskell><br />
import Data.Array.Storable<br />
import Foreign.Marshal.Alloc<br />
import Foreign.Marshal.Array<br />
import Foreign.ForeignPtr<br />
<br />
main = do ptr <- mallocArray 10<br />
fptr <- newForeignPtr_ ptr<br />
arr <- unsafeForeignPtrToStorableArray (1,10) fptr :: IO (StorableArray Int Int)<br />
writeArray arr 1 64<br />
a <- readArray arr 1<br />
print a<br />
free ptr<br />
</haskell><br />
<br />
This example allocates memory for 10 Ints (which emulates an array returned by some C function),<br />
then converts the returned 'Ptr Int' to 'ForeignPtr Int' and 'ForeignPtr Int' to<br />
'StorableArray Int Int'. It then writes and reads the first element of the array. At the end, the<br />
memory used by the array is deallocated by 'free', which again emulates deallocation<br />
by C routines. We can also enable the automatic freeing of the allocated block by replacing<br />
"newForeignPtr_ ptr" with "newForeignPtr finalizerFree ptr". In this case memory will be <br />
automatically freed after the last array usage, as for any other Haskell objects.<br />
<br />
<br />
== The Haskell Array Preprocessor (STPP) ==<br />
<br />
Using mutable (IO and ST) arrays in Haskell is not very handy.<br />
But there is one tool which adds syntactic sugar to make the use of such<br />
arrays very close to that of imperative languages. It is written by<br />
Hal Daume III and you can get it at<br />
http://hal3.name/STPP/stpp.tar.gz <br />
<br />
Using this tool, you can index array elements in arbitrarily complex<br />
expressions with the notation "arr[|i|]" and the preprocessor will<br />
automatically convert these forms to the appropriate calls to<br />
'readArray' and 'writeArray'. Multi-dimensional arrays are also<br />
supported, with indexing in the form "arr[|i|][|j|]". See further<br />
descriptions at http://hal3.name/STPP/.<br />
<br />
== Repa package ==<br />
Another option for arrays in Haskell which is worth consideration are REgular PArallel arrays (Repa). Repa is a Haskell library for high performance, regular, multi-dimensional parallel arrays. It allows to easily get an advantage from multi-core CPU's. Repa also provides list-like operations on arrays such as map, fold and zipWith, moreover repa arrays are instances of Num, which comes in hand for many applications.<br />
<br />
Repa employs a different syntax for arrays, which is also used in an experimental accelerate package. [http://hackage.haskell.org/package/accelerate Data.Array.Accelerate] is aimed to gain the performance from using GPGPU (via CUDA).<br />
<br />
Repa possesses a number of other interesting features, such as exporting/importing arrays from ascii or bmp files. For further information consult [[Numeric_Haskell:_A_Repa_Tutorial | repa tutorial]].<br />
<br />
== ArrayRef library ==<br />
<br />
The [http://haskell.org/haskellwiki/Library/ArrayRef#Reimplemented_Arrays_library ArrayRef library] reimplements array libraries with the following extensions:<br />
<br />
* dynamic (resizable) arrays<br />
* polymorphic unboxed arrays<br />
<br />
It also adds [http://haskell.org/haskellwiki/Library/ArrayRef#Syntax_sugar_for_mutable_types syntactic sugar]<br />
which simplifies arrays usage. Although not<br />
as elegant as STPP, it is implemented entirely<br />
inside the Haskell language without requiring any preprocessors.<br />
<br />
<br />
== Unsafe indexing, freezing/thawing, running over array elements ==<br />
<br />
There are operations that convert between mutable and immutable<br />
arrays of the same type, namely 'freeze' (mutable->immutable) and<br />
'thaw' (immutable->mutable). They make a new copy of the array. If you are<br />
sure that a mutable array will not be modified or that an immutable array will<br />
not be used after the conversion, you can use unsafeFreeze/unsafeThaw.<br />
These operations convert array the in-place if the input and resulting<br />
arrays have the the same memory representation (i.e. the same type and<br />
boxing). Please note that the "unsafe*" operations modify memory - they<br />
set/clear a flag in the array header which specifies array mutability.<br />
So these operations can't be used together with multi-threaded access<br />
to arrays (using threads or some form of coroutines).<br />
<br />
There are also operations that convert unboxed arrays to another<br />
element type, namely castIOUArray and castSTUArray. These operations<br />
rely on the actual type representation in memory and therefore there are no<br />
guarantees on their results. In particular, these operations can<br />
be used to convert any unboxable value to a sequence of bytes and<br />
vice versa. For example, they are used in the AltBinary library to serialize<br />
floating-point values. Please note that these operations don't<br />
recompute array bounds to reflect any changes in element size. You<br />
need to do that yourself using the 'sizeOf' operation.<br />
<br />
<br />
While arrays can have any type of index, the internal representation only accepts Ints for indexing. The array libraries first use the Ix class to translate the polymorphic index into an Int. An internal indexing function is then called on this Int index. The internal functions are: unsafeAt, unsafeRead and unsafeWrite, found in the Data.Array.Base module.<br />
You can use these operations yourself in order to speed up your program by avoiding bounds checking. These functions are marked "unsafe" for good a reason -- they allow the programmer to access and overwrite arbitrary addresses in memory. These operations are especially useful<br />
if you need to walk through entire array:<br />
<br />
<haskell><br />
import Data.Array.Base (unsafeAt)<br />
-- | Returns a list of all the elements of an array, in the same order<br />
-- as their indices.<br />
elems arr = [ unsafeAt arr i<br />
| i <- [0 .. rangeSize(bounds arr)-1] ]<br />
</haskell><br />
<br />
"unsafe*" operations in such loops are really safe because 'i' loops<br />
only through positions of existing array elements.<br />
<br />
<br />
== [[GHC]]-specific topics ==<br />
=== Parallel arrays (module GHC.PArr) ===<br />
<br />
As we already mentioned, array library supports two array varieties -<br />
lazy boxed arrays and strict unboxed ones. A parallel array implements<br />
something intermediate: it's a strict boxed immutable array. This<br />
keeps the flexibility of using any data type as an array element while making<br />
both creation of and access to such arrays much faster. Array creation is<br />
implemented as one imperative loop that fills all the array elements,<br />
while accesses to array elements don't need to check the "box". It should be<br />
obvious that parallel arrays are not efficient in cases where the<br />
calculation of array elements is relatively complex and most elements<br />
will not be used. One more drawback of practical usage is that<br />
parallel arrays don't support the IArray interface, which means that you<br />
can't write generic algorithms which work both with Array and the parallel<br />
array constructor.<br />
<br />
Like many GHC extensions, this is described in a paper: [http://www.cse.unsw.edu.au/~chak/papers/CK03.html An Approach to Fast Arrays in Haskell], by Manuel M. T. Chakravarty and Gabriele Keller.<br />
<br />
You can also look at the sources of [http://darcs.haskell.org/packages/base/GHC/PArr.hs GHC.PArr] module, which contains a lot of comments.<br />
<br />
The special syntax for parallel arrays is enabled by "ghc -fparr" or "ghci -fparr" which is undocumented in the GHC 6.4.1 user manual.<br />
<br />
<br />
=== Welcome to the machine: Array#, MutableArray#, ByteArray#, MutableByteArray#, pinned and moveable byte arrays ===<br />
<br />
The GHC heap contains two kinds of objects. Some are just byte sequences,<br />
while the others are pointers to other objects (so-called "boxes"). This<br />
segregation allows the system to find chains of references when performing<br />
garbage collection and to update these pointers when memory used by the heap<br />
is compacted and objects are moved to new places. The internal (raw) GHC<br />
type Array# represents a sequence of object pointers (boxes). There is a<br />
low-level operation in the ST monad which allocates an array of specified size in the heap.<br />
Its type is something like (Int -> ST s Array#). The Array# type is used<br />
inside the Array type which represents boxed immutable arrays.<br />
<br />
There is a different type for '''mutable''' boxed arrays<br />
(IOArray/STArray), namely MutableArray#. A separate type for mutable<br />
arrays is required because of the 2-stage garbage collection mechanism.<br />
The internal representations of Array# and MutableArray# are the same<br />
apart from some flags in header, and this make possible to perform in-place<br />
convsion between MutableArray# and Array# (this is that<br />
unsafeFreeze and unsafeThaw operations do).<br />
<br />
Unboxed arrays are represented by the ByteArray# type. This is just a plain<br />
memory area in the Haskell heap, like a C array. There are two primitive operations<br />
that create a ByteArray# of specified size. One allocates memory in the<br />
normal heap and so this byte array can be moved when<br />
garbage collection occurs. This prevents the conversion of a ByteArray#<br />
to a plain memory pointer that can be used in C procedures (although<br />
it's still possible to pass a current ByteArray# pointer to an "'''unsafe'''<br />
foreign" procedure if the latter doesn't try to store this pointer somewhere).<br />
The second primitive allocates a ByteArray# of a specified size in the<br />
"pinned" heap area, which contains objects with a fixed location. Such a byte<br />
array will never be moved by garbage collection, so its address can be used as a plain<br />
Ptr and shared with the C world. The first way to create ByteArray# is used<br />
inside the implementation of all UArray types, while the second way is used in<br />
StorableArray (although StorableArray can also point to data<br />
allocated by C malloc). Pinned ByteArray# also used in ByteString.<br />
<br />
There is also a MutableByteArray# type which is very similar to ByteArray#, but GHC's primitives support only monadic read/write<br />
operations for MutableByteArray#, and only pure reads for ByteArray#,<br />
as well as the unsafeFreeze/unsafeThaw operations which change appropriate<br />
fields in headers of this arrays. This differentiation doesn't make much<br />
sense except for additional safety checks.<br />
<br />
So, pinned MutableByteArray# or C malloced memory is used inside<br />
StorableArray, pinned ByteArray# or C malloced memory - inside<br />
ByteString, unpinned MutableByteArray# - inside IOUArray and<br />
STUArray, and unpinned ByteArray# is used inside UArray.<br />
<br />
The API's of boxed and unboxed arrays API are almost identical:<br />
<br />
marr <- alloc n - allocates a mutable array of the given size<br />
arr <- unsafeFreeze marr - converts a mutable array to an immutable one<br />
marr <- unsafeThaw arr - converts an immutable array to a mutable one<br />
x <- unsafeRead marr i - monadic reading of the value with the given index from a mutable array<br />
unsafeWrite marr i x - monadic writing of the value with the given index from a mutable array<br />
let x = unsafeAt arr i - pure reading of the value with the given index from an immutable array<br />
(all indices are counted from 0)<br />
<br />
Based on these primitive operations, the array library implements<br />
indexing with any type and with any lower bound, bounds checking and<br />
all other high-level operations. Operations that create<br />
immutable arrays just create them as mutable arrays in the ST monad, make<br />
all required updates on this array, and then use unsafeFreeze before<br />
returning the array from runST. Operations on IO arrays are implemented<br />
via operations on ST arrays using the stToIO operation.<br />
<br />
=== Mutable arrays and GC ===<br />
<br />
GHC implements 2-stage GC which is very fast. Minor GC occurs after<br />
each 256 kb allocated and scans only this area (plus recent stack<br />
frames) when searching for "live" data. This solution uses the fact<br />
that normal Haskell data are immutable and therefore any data<br />
structures created before the previous minor GC can't point to<br />
data structures created after it, since due to immutability, data<br />
can contain only "backward" references.<br />
<br />
But this simplicity breaks down when we add to the language mutable<br />
boxed references (IORef/STRef) and arrays (IOArray/STArray).<br />
On each GC, including minor ones, each element in a<br />
mutable data structure has to be be scanned because it may have been updated<br />
since the last GC and to make it point to data allocated since then.<br />
<br />
For programs that contain a lot of data in mutable boxed<br />
arrays/references, GC times may easily outweigh the useful computation time.<br />
Ironically, one such program is GHC itself.<br />
The solution for such programs is to add to a command line option like "+RTS -A10m", <br />
which increases the size of minor GC chunks from 256 kb to 10 mb, <br />
making minor GC 40 times less frequent. You can see effect of this<br />
change by using "+RTS -sstderr" option: "%GC time" should significantly decrease.<br />
<br />
There is a way to include this option in your executable so that it will<br />
be used automatically on each execution - you should just add to your<br />
the following line to your project C source file:<br />
<br />
char *ghc_rts_opts = "-A10m";<br />
<br />
Of course, you can increase or decrease this value according to your needs.<br />
<br />
Increasing "-A" value doesn't comes for free. Aside from the obvious<br />
increase in memory usage, execution times (of useful code) will also<br />
grow. The default "-A" value is tuned to be close to modern CPU cache sizes, so that most memory references fall inside the cache.<br />
When 10 mb of memory are allocated before doing GC, this data locality<br />
no longer holds. So increasing "-A" can either increase or decrease<br />
program speed. You should try various settings between<br />
64 kb and 16 mb while the running program with "typical" parameters and<br />
try to select the best setting for your specific program and CPU combination.<br />
<br />
There is also another way to avoid increasing GC times: use either<br />
unboxed or immutable arrays. Also note that immutable arrays are built<br />
as mutable ones and then "frozen", so during the construction time GC<br />
will also scan their contents.<br />
<br />
Hopefully, GHC 6.6 has fixed the problem - it remembers which<br />
references/arrays were updated since last GC and scans only them. You<br />
can suffer from the old problems only if you use very<br />
large arrays.<br />
<br />
Further information:<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html RTS options to control the garbage collector]<br />
* [http://hackage.haskell.org/trac/ghc/ticket/650 Problem description by Simon Marlow and report about GHC 6.6 improvements in this area]<br />
* [http://hackage.haskell.org/trac/ghc/wiki/GarbageCollectorNotes Notes about GHC garbage collector]<br />
* [http://research.microsoft.com/~simonpj/Papers/papers.html#gc Papers about GHC garbage collector]<br />
<br />
<br />
== Notes for contributors to this page ==<br />
if you have any questions, please<br />
ask at the IRC/mailing list. If you have any answers, please submit them<br />
directly to this page. please don't sign your contributions, so that<br />
anyone will feel free to further improve this page. but if you are<br />
compiler/Array libraries author - please sign your text to let us know<br />
that it is the Last Word of Truth :-)<br />
<br />
[[Category:Tutorials]]</div>Drbbhttps://wiki.haskell.org/index.php?title=Stack_overflow&diff=44018Stack overflow2012-01-16T20:41:00Z<p>Drbb: /* Scans */</p>
<hr />
<div>[[Category:Tutorials]]<br />
<br />
<br />
There is no call stack in Haskell. Instead we find a <br />
pattern matching stack whose entries are essentially case <br />
expressions waiting for their scrutinee to be evaluated enough <br />
that they can match a constructor (WHNF).<br />
<br />
When GHC is evaluating a thunked expression it uses an<br />
internal stack. This inner stack for thunk evaluation <br />
is the one that can overflow in practice.<br />
<br />
<br />
== Folds ==<br />
<br />
First, read [[Performance/Accumulating parameter]]. If you are not writing your code [[tail recursion|tail-recursively]], then that is why you are getting stack overflows. However, making code tail-recursive in a lazy language is not quite the same as in a eager language. This page is more geared to the latter case using foldr/l as the prime culprit/example. As such [[Fold]] may be helpful, but isn't too critical. Also knowing what <hask>seq</hask> and <hask>($!)</hask> do, as covered in [http://users.aber.ac.uk/afc/stricthaskell.html#seq Making Haskell programs faster and smaller] and in the [http://haskell.org/onlinereport/ Haskell Report] is necessary.<br />
<br />
The definitions of the three folds we'll be looking at are as follows:<br />
<haskell><br />
foldr f z [] = z<br />
foldr f z (x:xs) = f x (foldr f z xs)<br />
<br />
foldl f z [] = z<br />
foldl f z (x:xs) = foldl f (f z x) xs<br />
<br />
foldl' f z [] = z<br />
foldl' f z (x:xs) = (foldl' f $! f z x) xs<br />
<br />
foldl' (found in e.g. Data.List) is just a stricter version of foldl.<br />
</haskell><br />
The one-line summary for folds: if the binary operation is strict use foldl', otherwise use foldr.<br />
<br />
----<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldr (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
If you've read [[Performance/Accumulating parameter]], you should immediately see the problem from the definition of foldr above. Quite simply, foldr isn't tail-recursive! But,<br />
<haskell><br />
concat xss = foldr (++) [] xss<br />
</haskell><br />
This is from the Haskell Report. Surely they know what they are doing! And sure enough,<br />
<haskell><br />
main = print (length (concat [[x] | x <- [1..1000000]]))<br />
</haskell><br />
works fine.<br />
<br />
Less common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl (+) 0 -- foldl instead of foldr this time<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
So what's going on here? Looking at the code for foldl, it looks tail-recursive. Well, much like you can see the problem with a non-tail-recursive factorial by unfolding a few iterations, let's do the same for our foldl definition of sum, but making sure to use a call-by-name/need evaluation order. Here is the unfolding,<br />
<haskell><br />
mysum [1..10] -><br />
foldl (+) 0 (1:[2..10]) -><br />
foldl (+) (0+1) (2:[3..10]) -><br />
foldl (+) (0+1+2) (3:[4..10]) -><br />
foldl (+) (0+1+2+3) (4:[5..10]) -> ...<br />
</haskell><br />
I think you get the idea. The problem is that we are building up a chain of thunks that will evaluate the sum instead of just maintaining a running sum. What we need to do is to force the addition before recursing. This is exactly what foldl' does.<br />
<br />
Just to check,<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl' (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
works fine.<br />
<br />
Now let's go back to the foldr sum and concat. What's the difference between sum and concat that makes the sum definition wrong, but the concat definition right. Again, let's evaluate each by hand.<br />
<haskell><br />
mysum (+) 0 [1..10] -><br />
foldr (+) 0 (1:[2..10]) -><br />
1+foldr (+) 0 (2:[3..10]) -><br />
1+(2+foldr (+) 0 (3:[4..10])) -> ...<br />
</haskell><br />
Okay, no surprise there.<br />
<haskell><br />
concat [[1],[2],[3],...] -><br />
foldr (++) [] ([1]:[[2],[3],...]) -><br />
(1:[])++foldr (++) [] [[2],[3],...] -><br />
1:([]++foldr (++) [] [[2],[3],...])<br />
</haskell><br />
Notice that there is no '-> ...' at the end. That was the complete evaluation. There is no reason to do anything more, unless we look at the result. We may well GC the 1 before we look at the tail, and GC the first cons cell before we look at the second. So, concat runs in a constant amount of stack and further can handle infinite lists (as a note, it's immediately obvious foldl(') can never work on infinite lists because we'll always be in the (:) case and that always immediately recurses). The differentiator between mysum and concat is that (++) is not strict* in its second argument; we don't have to evaluate the rest of the foldr to know the beginning of concat. In mysum, since (+) is strict in its second argument, we need the results of the whole foldr before we can compute the final result.<br />
<br />
So, we arrive at the one-line summary: <br />
A function strict* in its second argument will always require linear stack space with foldr, so foldl' should be used instead in that case. <br />
If the function is lazy/non-strict in its second argument we should use foldr to 1) support infinite lists and 2) to allow a streaming use of the input list where only part of it needs to be in memory at a time.<br />
<br />
Okay, both here and in the one-line summary, there is no mention of foldl. When should foldl be used? The pragmatic answer is: by and far, it shouldn't be used. A case where it makes a difference is if the function is conditionally strict in its first argument depending on its second, where I use conditionally strict to mean a function that is strict or not in one argument depending on another argument(s). For an example, consider a definition of <hask>(*)</hask> that builds up ASTs of arithmetic expressions and incorporates a simplification (<hask>a*0 = 0</hask> and then <hask>0*a = 0</hask>); then if <hask>product</hask> is defined by <hask>foldl (*) 1</hask>, <hask>product [</hask>&perp;<hask>,0]</hask> will terminate with 0 while a definition in terms of <hask>foldl'</hask> wouldn't. However, I can't think of a really convincing example. In most cases, foldl' is what you want.<br />
<br />
<nowiki>*</nowiki> A strict function is a function <hask>f</hask>, such that <hask>f </hask>&perp;<hask> = </hask>&perp;. Typically, we think of a function "being strict" in an argument as a function that "forces" its argument, but the above definition of strict should immediately suggest another function that is strict and doesn't "force" it's argument in the intuitive sense, namely id. <hask>([]++) = id</hask> and therefore is a strict function. Sure enough, if you were to evaluate <hask>(concat (repeat []))</hask> it would not terminate. As such, <hask>(++)</hask> is a conditionally strict function. This also makes the "always" slightly imprecise, a function that is strict because it just returns it's argument, will not use up stack space (but is, as mentioned, still an issue for infinitely long lists).<br />
<br />
== Weak Head Normal Form ==<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
People who understand seq and weak head normal form (whnf) can immediately understand what goes wrong here. <hask>(acc+x, len+1)</hask> is already in whnf, so the <hask>seq</hask> (in the definition of <hask>foldl'</hask>), which reduces a value to whnf, does nothing to this. This code will build up thunks just like the original <hask>foldl</hask> example, they'll just be inside a tuple. <br />
<br />
For the same reason, this won't help either:<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc, len) `seq` (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
A deeper `seq` is needed. The solution is to force the components of the tuple, e.g.<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)<br />
</haskell><br />
or more clearly and concisely using a recent GHC extension<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(!acc, !len) x -> (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
== Scans ==<br />
<br />
A subtle stack-overflow surprise comes when<br />
<haskell><br />
print (scanl (+) 0 [1..1000000])<br />
</haskell><br />
completes successfully but<br />
<haskell><br />
print (last (scanl (+) 0 [1..1000000]))<br />
</haskell><br />
causes a stack overflow.<br />
<br />
The latter stack overflow is explained exactly as before, namely,<br />
<haskell><br />
last (scanl (+) 0 [1..5]) -><br />
... several steps ... -><br />
((((0+1)+2)+3)+4)+5<br />
</haskell><br />
This is exactly like <hask>foldl</hask>, building a deep thunk, then evaluating, needing much stack.<br />
<br />
Most puzzling is why the former succeeds without a stack overflow. This is caused by a combination of two factors:<br />
* thunks in the list produced by <hask>scanl</hask> enjoy sharing: late thunks build upon early thunks<br />
* printing a list of numbers evaluates early thunks and then late thunks<br />
To exemplify, here is an abridged progression. I use this pseudo format to depict sharing of thunks<br />
<haskell><br />
expr where var=expr, var=expr<br />
</haskell><br />
although in reality it is more like a pointer graph.<br />
<haskell><br />
print (scanl (+) 0 [1..1000000]) -><br />
print (a : case [1..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (a+x) xs) where a=0 -><br />
<nowiki>... evaluate a to 0 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (a+1) [2..1000000]) where a=0 -><br />
print (b : case [2..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (b+x) xs) where a=0, b=a+1 -><br />
<nowiki>... evaluate b to 1 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (b+2) [3..1000000]) where b=1 -><br />
print (c : case [3..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (c+x) xs) where b=1, c=b+2 -><br />
<nowiki>... evaluate c to 3 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (c+3) [4..1000000]) where c=3 -><br />
print (d : case [4..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (d+x) xs) where c=3, d=c+3 -><br />
<nowiki>... evaluate d to 6 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (d+4) [5..1000000]) where d=6 -> etc.<br />
</haskell><br />
The important thing to watch is the life cycle of intermediate thunks, e.g., <hask>c</hask> is created at some point as a 1-level deep addition, then almost immediately reduced to a number out of necessity, before a later thunk <hask>d</hask> builds upon it. Therefore there is no growth and no stack overflow.<br />
<br />
In contrast, again, <hask>last (scanl (+) 0 [1..1000000])</hask> skips over to the last thunk right away. Since early items are not reduced yet, the last item remains a huge chain and causes overflow.<br />
<br />
As an addendum, there are three ways of handling this problem and similar ones:<br />
# You can have your traversal functions (in this case, last) force the list as it goes along.<br />
# You can use (perhaps custom) versions of the list (or data structure, in general) producing functions (in this case, scanl) that force the elements as it builds the data structure.<br />
# You can use a data structure that's strict in its elements, in this case it would be a head strict list.</div>Drbbhttps://wiki.haskell.org/index.php?title=Stack_overflow&diff=44017Stack overflow2012-01-16T20:40:27Z<p>Drbb: /* Weak Head Normal Form */ added exposition</p>
<hr />
<div>[[Category:Tutorials]]<br />
<br />
<br />
There is no call stack in Haskell. Instead we find a <br />
pattern matching stack whose entries are essentially case <br />
expressions waiting for their scrutinee to be evaluated enough <br />
that they can match a constructor (WHNF).<br />
<br />
When GHC is evaluating a thunked expression it uses an<br />
internal stack. This inner stack for thunk evaluation <br />
is the one that can overflow in practice.<br />
<br />
<br />
== Folds ==<br />
<br />
First, read [[Performance/Accumulating parameter]]. If you are not writing your code [[tail recursion|tail-recursively]], then that is why you are getting stack overflows. However, making code tail-recursive in a lazy language is not quite the same as in a eager language. This page is more geared to the latter case using foldr/l as the prime culprit/example. As such [[Fold]] may be helpful, but isn't too critical. Also knowing what <hask>seq</hask> and <hask>($!)</hask> do, as covered in [http://users.aber.ac.uk/afc/stricthaskell.html#seq Making Haskell programs faster and smaller] and in the [http://haskell.org/onlinereport/ Haskell Report] is necessary.<br />
<br />
The definitions of the three folds we'll be looking at are as follows:<br />
<haskell><br />
foldr f z [] = z<br />
foldr f z (x:xs) = f x (foldr f z xs)<br />
<br />
foldl f z [] = z<br />
foldl f z (x:xs) = foldl f (f z x) xs<br />
<br />
foldl' f z [] = z<br />
foldl' f z (x:xs) = (foldl' f $! f z x) xs<br />
<br />
foldl' (found in e.g. Data.List) is just a stricter version of foldl.<br />
</haskell><br />
The one-line summary for folds: if the binary operation is strict use foldl', otherwise use foldr.<br />
<br />
----<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldr (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
If you've read [[Performance/Accumulating parameter]], you should immediately see the problem from the definition of foldr above. Quite simply, foldr isn't tail-recursive! But,<br />
<haskell><br />
concat xss = foldr (++) [] xss<br />
</haskell><br />
This is from the Haskell Report. Surely they know what they are doing! And sure enough,<br />
<haskell><br />
main = print (length (concat [[x] | x <- [1..1000000]]))<br />
</haskell><br />
works fine.<br />
<br />
Less common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl (+) 0 -- foldl instead of foldr this time<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
So what's going on here? Looking at the code for foldl, it looks tail-recursive. Well, much like you can see the problem with a non-tail-recursive factorial by unfolding a few iterations, let's do the same for our foldl definition of sum, but making sure to use a call-by-name/need evaluation order. Here is the unfolding,<br />
<haskell><br />
mysum [1..10] -><br />
foldl (+) 0 (1:[2..10]) -><br />
foldl (+) (0+1) (2:[3..10]) -><br />
foldl (+) (0+1+2) (3:[4..10]) -><br />
foldl (+) (0+1+2+3) (4:[5..10]) -> ...<br />
</haskell><br />
I think you get the idea. The problem is that we are building up a chain of thunks that will evaluate the sum instead of just maintaining a running sum. What we need to do is to force the addition before recursing. This is exactly what foldl' does.<br />
<br />
Just to check,<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl' (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
works fine.<br />
<br />
Now let's go back to the foldr sum and concat. What's the difference between sum and concat that makes the sum definition wrong, but the concat definition right. Again, let's evaluate each by hand.<br />
<haskell><br />
mysum (+) 0 [1..10] -><br />
foldr (+) 0 (1:[2..10]) -><br />
1+foldr (+) 0 (2:[3..10]) -><br />
1+(2+foldr (+) 0 (3:[4..10])) -> ...<br />
</haskell><br />
Okay, no surprise there.<br />
<haskell><br />
concat [[1],[2],[3],...] -><br />
foldr (++) [] ([1]:[[2],[3],...]) -><br />
(1:[])++foldr (++) [] [[2],[3],...] -><br />
1:([]++foldr (++) [] [[2],[3],...])<br />
</haskell><br />
Notice that there is no '-> ...' at the end. That was the complete evaluation. There is no reason to do anything more, unless we look at the result. We may well GC the 1 before we look at the tail, and GC the first cons cell before we look at the second. So, concat runs in a constant amount of stack and further can handle infinite lists (as a note, it's immediately obvious foldl(') can never work on infinite lists because we'll always be in the (:) case and that always immediately recurses). The differentiator between mysum and concat is that (++) is not strict* in its second argument; we don't have to evaluate the rest of the foldr to know the beginning of concat. In mysum, since (+) is strict in its second argument, we need the results of the whole foldr before we can compute the final result.<br />
<br />
So, we arrive at the one-line summary: <br />
A function strict* in its second argument will always require linear stack space with foldr, so foldl' should be used instead in that case. <br />
If the function is lazy/non-strict in its second argument we should use foldr to 1) support infinite lists and 2) to allow a streaming use of the input list where only part of it needs to be in memory at a time.<br />
<br />
Okay, both here and in the one-line summary, there is no mention of foldl. When should foldl be used? The pragmatic answer is: by and far, it shouldn't be used. A case where it makes a difference is if the function is conditionally strict in its first argument depending on its second, where I use conditionally strict to mean a function that is strict or not in one argument depending on another argument(s). For an example, consider a definition of <hask>(*)</hask> that builds up ASTs of arithmetic expressions and incorporates a simplification (<hask>a*0 = 0</hask> and then <hask>0*a = 0</hask>); then if <hask>product</hask> is defined by <hask>foldl (*) 1</hask>, <hask>product [</hask>&perp;<hask>,0]</hask> will terminate with 0 while a definition in terms of <hask>foldl'</hask> wouldn't. However, I can't think of a really convincing example. In most cases, foldl' is what you want.<br />
<br />
<nowiki>*</nowiki> A strict function is a function <hask>f</hask>, such that <hask>f </hask>&perp;<hask> = </hask>&perp;. Typically, we think of a function "being strict" in an argument as a function that "forces" its argument, but the above definition of strict should immediately suggest another function that is strict and doesn't "force" it's argument in the intuitive sense, namely id. <hask>([]++) = id</hask> and therefore is a strict function. Sure enough, if you were to evaluate <hask>(concat (repeat []))</hask> it would not terminate. As such, <hask>(++)</hask> is a conditionally strict function. This also makes the "always" slightly imprecise, a function that is strict because it just returns it's argument, will not use up stack space (but is, as mentioned, still an issue for infinitely long lists).<br />
<br />
== Weak Head Normal Form ==<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
People who understand seq and weak head normal form (whnf) can immediately understand what goes wrong here. <hask>(acc+x, len+1)</hask> is already in whnf, so the <hask>seq</hask> (in the definition of <hask>foldl'</hask>), which reduces a value to whnf, does nothing to this. This code will build up thunks just like the original <hask>foldl</hask> example, they'll just be inside a tuple. <br />
<br />
For the same reason, this won't help either:<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc, len) `seq` (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
A deeper `seq` is needed. The solution is to force the components of the tuple, e.g.<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)<br />
</haskell><br />
or more clearly and concisely using a recent GHC extension<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(!acc, !len) x -> (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
== Scans ==<br />
<br />
A subtle stack-overflow surprise comes when<br />
<haskell><br />
print (scanl (+) 0 [1..1000000])<br />
</haskell><br />
completes successfully but<br />
<haskell><br />
print (last (scanl (+) 0 [1..1000000]))<br />
</haskell><br />
causes a stack overflow.<br />
<br />
The latter stack overflow is explained exactly as before, namely,<br />
<haskell><br />
last (scanl (+) 0 [1..5]) -><br />
<nowiki>... several steps ...</nowiki> -><br />
((((0+1)+2)+3)+4)+5<br />
</haskell><br />
This is exactly like <hask>foldl</hask>, building a deep thunk, then evaluating, needing much stack.<br />
<br />
Most puzzling is why the former succeeds without a stack overflow. This is caused by a combination of two factors:<br />
* thunks in the list produced by <hask>scanl</hask> enjoy sharing: late thunks build upon early thunks<br />
* printing a list of numbers evaluates early thunks and then late thunks<br />
To exemplify, here is an abridged progression. I use this pseudo format to depict sharing of thunks<br />
<haskell><br />
expr where var=expr, var=expr<br />
</haskell><br />
although in reality it is more like a pointer graph.<br />
<haskell><br />
print (scanl (+) 0 [1..1000000]) -><br />
print (a : case [1..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (a+x) xs) where a=0 -><br />
<nowiki>... evaluate a to 0 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (a+1) [2..1000000]) where a=0 -><br />
print (b : case [2..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (b+x) xs) where a=0, b=a+1 -><br />
<nowiki>... evaluate b to 1 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (b+2) [3..1000000]) where b=1 -><br />
print (c : case [3..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (c+x) xs) where b=1, c=b+2 -><br />
<nowiki>... evaluate c to 3 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (c+3) [4..1000000]) where c=3 -><br />
print (d : case [4..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (d+x) xs) where c=3, d=c+3 -><br />
<nowiki>... evaluate d to 6 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (d+4) [5..1000000]) where d=6 -> etc.<br />
</haskell><br />
The important thing to watch is the life cycle of intermediate thunks, e.g., <hask>c</hask> is created at some point as a 1-level deep addition, then almost immediately reduced to a number out of necessity, before a later thunk <hask>d</hask> builds upon it. Therefore there is no growth and no stack overflow.<br />
<br />
In contrast, again, <hask>last (scanl (+) 0 [1..1000000])</hask> skips over to the last thunk right away. Since early items are not reduced yet, the last item remains a huge chain and causes overflow.<br />
<br />
As an addendum, there are three ways of handling this problem and similar ones:<br />
# You can have your traversal functions (in this case, last) force the list as it goes along.<br />
# You can use (perhaps custom) versions of the list (or data structure, in general) producing functions (in this case, scanl) that force the elements as it builds the data structure.<br />
# You can use a data structure that's strict in its elements, in this case it would be a head strict list.</div>Drbbhttps://wiki.haskell.org/index.php?title=Stack_overflow&diff=44016Stack overflow2012-01-16T20:36:53Z<p>Drbb: /* Weak Head Normal Form */</p>
<hr />
<div>[[Category:Tutorials]]<br />
<br />
<br />
There is no call stack in Haskell. Instead we find a <br />
pattern matching stack whose entries are essentially case <br />
expressions waiting for their scrutinee to be evaluated enough <br />
that they can match a constructor (WHNF).<br />
<br />
When GHC is evaluating a thunked expression it uses an<br />
internal stack. This inner stack for thunk evaluation <br />
is the one that can overflow in practice.<br />
<br />
<br />
== Folds ==<br />
<br />
First, read [[Performance/Accumulating parameter]]. If you are not writing your code [[tail recursion|tail-recursively]], then that is why you are getting stack overflows. However, making code tail-recursive in a lazy language is not quite the same as in a eager language. This page is more geared to the latter case using foldr/l as the prime culprit/example. As such [[Fold]] may be helpful, but isn't too critical. Also knowing what <hask>seq</hask> and <hask>($!)</hask> do, as covered in [http://users.aber.ac.uk/afc/stricthaskell.html#seq Making Haskell programs faster and smaller] and in the [http://haskell.org/onlinereport/ Haskell Report] is necessary.<br />
<br />
The definitions of the three folds we'll be looking at are as follows:<br />
<haskell><br />
foldr f z [] = z<br />
foldr f z (x:xs) = f x (foldr f z xs)<br />
<br />
foldl f z [] = z<br />
foldl f z (x:xs) = foldl f (f z x) xs<br />
<br />
foldl' f z [] = z<br />
foldl' f z (x:xs) = (foldl' f $! f z x) xs<br />
<br />
foldl' (found in e.g. Data.List) is just a stricter version of foldl.<br />
</haskell><br />
The one-line summary for folds: if the binary operation is strict use foldl', otherwise use foldr.<br />
<br />
----<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldr (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
If you've read [[Performance/Accumulating parameter]], you should immediately see the problem from the definition of foldr above. Quite simply, foldr isn't tail-recursive! But,<br />
<haskell><br />
concat xss = foldr (++) [] xss<br />
</haskell><br />
This is from the Haskell Report. Surely they know what they are doing! And sure enough,<br />
<haskell><br />
main = print (length (concat [[x] | x <- [1..1000000]]))<br />
</haskell><br />
works fine.<br />
<br />
Less common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl (+) 0 -- foldl instead of foldr this time<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
So what's going on here? Looking at the code for foldl, it looks tail-recursive. Well, much like you can see the problem with a non-tail-recursive factorial by unfolding a few iterations, let's do the same for our foldl definition of sum, but making sure to use a call-by-name/need evaluation order. Here is the unfolding,<br />
<haskell><br />
mysum [1..10] -><br />
foldl (+) 0 (1:[2..10]) -><br />
foldl (+) (0+1) (2:[3..10]) -><br />
foldl (+) (0+1+2) (3:[4..10]) -><br />
foldl (+) (0+1+2+3) (4:[5..10]) -> ...<br />
</haskell><br />
I think you get the idea. The problem is that we are building up a chain of thunks that will evaluate the sum instead of just maintaining a running sum. What we need to do is to force the addition before recursing. This is exactly what foldl' does.<br />
<br />
Just to check,<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl' (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
works fine.<br />
<br />
Now let's go back to the foldr sum and concat. What's the difference between sum and concat that makes the sum definition wrong, but the concat definition right. Again, let's evaluate each by hand.<br />
<haskell><br />
mysum (+) 0 [1..10] -><br />
foldr (+) 0 (1:[2..10]) -><br />
1+foldr (+) 0 (2:[3..10]) -><br />
1+(2+foldr (+) 0 (3:[4..10])) -> ...<br />
</haskell><br />
Okay, no surprise there.<br />
<haskell><br />
concat [[1],[2],[3],...] -><br />
foldr (++) [] ([1]:[[2],[3],...]) -><br />
(1:[])++foldr (++) [] [[2],[3],...] -><br />
1:([]++foldr (++) [] [[2],[3],...])<br />
</haskell><br />
Notice that there is no '-> ...' at the end. That was the complete evaluation. There is no reason to do anything more, unless we look at the result. We may well GC the 1 before we look at the tail, and GC the first cons cell before we look at the second. So, concat runs in a constant amount of stack and further can handle infinite lists (as a note, it's immediately obvious foldl(') can never work on infinite lists because we'll always be in the (:) case and that always immediately recurses). The differentiator between mysum and concat is that (++) is not strict* in its second argument; we don't have to evaluate the rest of the foldr to know the beginning of concat. In mysum, since (+) is strict in its second argument, we need the results of the whole foldr before we can compute the final result.<br />
<br />
So, we arrive at the one-line summary: <br />
A function strict* in its second argument will always require linear stack space with foldr, so foldl' should be used instead in that case. <br />
If the function is lazy/non-strict in its second argument we should use foldr to 1) support infinite lists and 2) to allow a streaming use of the input list where only part of it needs to be in memory at a time.<br />
<br />
Okay, both here and in the one-line summary, there is no mention of foldl. When should foldl be used? The pragmatic answer is: by and far, it shouldn't be used. A case where it makes a difference is if the function is conditionally strict in its first argument depending on its second, where I use conditionally strict to mean a function that is strict or not in one argument depending on another argument(s). For an example, consider a definition of <hask>(*)</hask> that builds up ASTs of arithmetic expressions and incorporates a simplification (<hask>a*0 = 0</hask> and then <hask>0*a = 0</hask>); then if <hask>product</hask> is defined by <hask>foldl (*) 1</hask>, <hask>product [</hask>&perp;<hask>,0]</hask> will terminate with 0 while a definition in terms of <hask>foldl'</hask> wouldn't. However, I can't think of a really convincing example. In most cases, foldl' is what you want.<br />
<br />
<nowiki>*</nowiki> A strict function is a function <hask>f</hask>, such that <hask>f </hask>&perp;<hask> = </hask>&perp;. Typically, we think of a function "being strict" in an argument as a function that "forces" its argument, but the above definition of strict should immediately suggest another function that is strict and doesn't "force" it's argument in the intuitive sense, namely id. <hask>([]++) = id</hask> and therefore is a strict function. Sure enough, if you were to evaluate <hask>(concat (repeat []))</hask> it would not terminate. As such, <hask>(++)</hask> is a conditionally strict function. This also makes the "always" slightly imprecise, a function that is strict because it just returns it's argument, will not use up stack space (but is, as mentioned, still an issue for infinitely long lists).<br />
<br />
== Weak Head Normal Form ==<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
This attempt to fix the problem doesn't help:<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc, len) `seq` (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
People who understand seq and weak head normal form (whnf) can immediately understand what goes wrong here. <hask>(acc+x, len+1)</hask> is already in whnf, so <hask>seq</hask>, which reduces a value to whnf, does nothing to this. This code will build up thunks just like the original <hask>foldl</hask> example, they'll just be inside a tuple. The solution is just to force the components of the tuple, e.g.<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)<br />
</haskell><br />
or more clearly and concisely using a recent GHC extension<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(!acc, !len) x -> (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
== Scans ==<br />
<br />
A subtle stack-overflow surprise comes when<br />
<haskell><br />
print (scanl (+) 0 [1..1000000])<br />
</haskell><br />
completes successfully but<br />
<haskell><br />
print (last (scanl (+) 0 [1..1000000]))<br />
</haskell><br />
causes a stack overflow.<br />
<br />
The latter stack overflow is explained exactly as before, namely,<br />
<haskell><br />
last (scanl (+) 0 [1..5]) -><br />
<nowiki>... several steps ...</nowiki> -><br />
((((0+1)+2)+3)+4)+5<br />
</haskell><br />
This is exactly like <hask>foldl</hask>, building a deep thunk, then evaluating, needing much stack.<br />
<br />
Most puzzling is why the former succeeds without a stack overflow. This is caused by a combination of two factors:<br />
* thunks in the list produced by <hask>scanl</hask> enjoy sharing: late thunks build upon early thunks<br />
* printing a list of numbers evaluates early thunks and then late thunks<br />
To exemplify, here is an abridged progression. I use this pseudo format to depict sharing of thunks<br />
<haskell><br />
expr where var=expr, var=expr<br />
</haskell><br />
although in reality it is more like a pointer graph.<br />
<haskell><br />
print (scanl (+) 0 [1..1000000]) -><br />
print (a : case [1..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (a+x) xs) where a=0 -><br />
<nowiki>... evaluate a to 0 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (a+1) [2..1000000]) where a=0 -><br />
print (b : case [2..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (b+x) xs) where a=0, b=a+1 -><br />
<nowiki>... evaluate b to 1 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (b+2) [3..1000000]) where b=1 -><br />
print (c : case [3..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (c+x) xs) where b=1, c=b+2 -><br />
<nowiki>... evaluate c to 3 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (c+3) [4..1000000]) where c=3 -><br />
print (d : case [4..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (d+x) xs) where c=3, d=c+3 -><br />
<nowiki>... evaluate d to 6 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (d+4) [5..1000000]) where d=6 -> etc.<br />
</haskell><br />
The important thing to watch is the life cycle of intermediate thunks, e.g., <hask>c</hask> is created at some point as a 1-level deep addition, then almost immediately reduced to a number out of necessity, before a later thunk <hask>d</hask> builds upon it. Therefore there is no growth and no stack overflow.<br />
<br />
In contrast, again, <hask>last (scanl (+) 0 [1..1000000])</hask> skips over to the last thunk right away. Since early items are not reduced yet, the last item remains a huge chain and causes overflow.<br />
<br />
As an addendum, there are three ways of handling this problem and similar ones:<br />
# You can have your traversal functions (in this case, last) force the list as it goes along.<br />
# You can use (perhaps custom) versions of the list (or data structure, in general) producing functions (in this case, scanl) that force the elements as it builds the data structure.<br />
# You can use a data structure that's strict in its elements, in this case it would be a head strict list.</div>Drbbhttps://wiki.haskell.org/index.php?title=Stack_overflow&diff=44015Stack overflow2012-01-16T18:47:02Z<p>Drbb: </p>
<hr />
<div>[[Category:Tutorials]]<br />
<br />
<br />
There is no call stack in Haskell. Instead we find a <br />
pattern matching stack whose entries are essentially case <br />
expressions waiting for their scrutinee to be evaluated enough <br />
that they can match a constructor (WHNF).<br />
<br />
When GHC is evaluating a thunked expression it uses an<br />
internal stack. This inner stack for thunk evaluation <br />
is the one that can overflow in practice.<br />
<br />
<br />
== Folds ==<br />
<br />
First, read [[Performance/Accumulating parameter]]. If you are not writing your code [[tail recursion|tail-recursively]], then that is why you are getting stack overflows. However, making code tail-recursive in a lazy language is not quite the same as in a eager language. This page is more geared to the latter case using foldr/l as the prime culprit/example. As such [[Fold]] may be helpful, but isn't too critical. Also knowing what <hask>seq</hask> and <hask>($!)</hask> do, as covered in [http://users.aber.ac.uk/afc/stricthaskell.html#seq Making Haskell programs faster and smaller] and in the [http://haskell.org/onlinereport/ Haskell Report] is necessary.<br />
<br />
The definitions of the three folds we'll be looking at are as follows:<br />
<haskell><br />
foldr f z [] = z<br />
foldr f z (x:xs) = f x (foldr f z xs)<br />
<br />
foldl f z [] = z<br />
foldl f z (x:xs) = foldl f (f z x) xs<br />
<br />
foldl' f z [] = z<br />
foldl' f z (x:xs) = (foldl' f $! f z x) xs<br />
<br />
foldl' (found in e.g. Data.List) is just a stricter version of foldl.<br />
</haskell><br />
The one-line summary for folds: if the binary operation is strict use foldl', otherwise use foldr.<br />
<br />
----<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldr (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
If you've read [[Performance/Accumulating parameter]], you should immediately see the problem from the definition of foldr above. Quite simply, foldr isn't tail-recursive! But,<br />
<haskell><br />
concat xss = foldr (++) [] xss<br />
</haskell><br />
This is from the Haskell Report. Surely they know what they are doing! And sure enough,<br />
<haskell><br />
main = print (length (concat [[x] | x <- [1..1000000]]))<br />
</haskell><br />
works fine.<br />
<br />
Less common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl (+) 0 -- foldl instead of foldr this time<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
So what's going on here? Looking at the code for foldl, it looks tail-recursive. Well, much like you can see the problem with a non-tail-recursive factorial by unfolding a few iterations, let's do the same for our foldl definition of sum, but making sure to use a call-by-name/need evaluation order. Here is the unfolding,<br />
<haskell><br />
mysum [1..10] -><br />
foldl (+) 0 (1:[2..10]) -><br />
foldl (+) (0+1) (2:[3..10]) -><br />
foldl (+) (0+1+2) (3:[4..10]) -><br />
foldl (+) (0+1+2+3) (4:[5..10]) -> ...<br />
</haskell><br />
I think you get the idea. The problem is that we are building up a chain of thunks that will evaluate the sum instead of just maintaining a running sum. What we need to do is to force the addition before recursing. This is exactly what foldl' does.<br />
<br />
Just to check,<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl' (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
works fine.<br />
<br />
Now let's go back to the foldr sum and concat. What's the difference between sum and concat that makes the sum definition wrong, but the concat definition right. Again, let's evaluate each by hand.<br />
<haskell><br />
mysum (+) 0 [1..10] -><br />
foldr (+) 0 (1:[2..10]) -><br />
1+foldr (+) 0 (2:[3..10]) -><br />
1+(2+foldr (+) 0 (3:[4..10])) -> ...<br />
</haskell><br />
Okay, no surprise there.<br />
<haskell><br />
concat [[1],[2],[3],...] -><br />
foldr (++) [] ([1]:[[2],[3],...]) -><br />
(1:[])++foldr (++) [] [[2],[3],...] -><br />
1:([]++foldr (++) [] [[2],[3],...])<br />
</haskell><br />
Notice that there is no '-> ...' at the end. That was the complete evaluation. There is no reason to do anything more, unless we look at the result. We may well GC the 1 before we look at the tail, and GC the first cons cell before we look at the second. So, concat runs in a constant amount of stack and further can handle infinite lists (as a note, it's immediately obvious foldl(') can never work on infinite lists because we'll always be in the (:) case and that always immediately recurses). The differentiator between mysum and concat is that (++) is not strict* in its second argument; we don't have to evaluate the rest of the foldr to know the beginning of concat. In mysum, since (+) is strict in its second argument, we need the results of the whole foldr before we can compute the final result.<br />
<br />
So, we arrive at the one-line summary: <br />
A function strict* in its second argument will always require linear stack space with foldr, so foldl' should be used instead in that case. <br />
If the function is lazy/non-strict in its second argument we should use foldr to 1) support infinite lists and 2) to allow a streaming use of the input list where only part of it needs to be in memory at a time.<br />
<br />
Okay, both here and in the one-line summary, there is no mention of foldl. When should foldl be used? The pragmatic answer is: by and far, it shouldn't be used. A case where it makes a difference is if the function is conditionally strict in its first argument depending on its second, where I use conditionally strict to mean a function that is strict or not in one argument depending on another argument(s). For an example, consider a definition of <hask>(*)</hask> that builds up ASTs of arithmetic expressions and incorporates a simplification (<hask>a*0 = 0</hask> and then <hask>0*a = 0</hask>); then if <hask>product</hask> is defined by <hask>foldl (*) 1</hask>, <hask>product [</hask>&perp;<hask>,0]</hask> will terminate with 0 while a definition in terms of <hask>foldl'</hask> wouldn't. However, I can't think of a really convincing example. In most cases, foldl' is what you want.<br />
<br />
<nowiki>*</nowiki> A strict function is a function <hask>f</hask>, such that <hask>f </hask>&perp;<hask> = </hask>&perp;. Typically, we think of a function "being strict" in an argument as a function that "forces" its argument, but the above definition of strict should immediately suggest another function that is strict and doesn't "force" it's argument in the intuitive sense, namely id. <hask>([]++) = id</hask> and therefore is a strict function. Sure enough, if you were to evaluate <hask>(concat (repeat []))</hask> it would not terminate. As such, <hask>(++)</hask> is a conditionally strict function. This also makes the "always" slightly imprecise, a function that is strict because it just returns it's argument, will not use up stack space (but is, as mentioned, still an issue for infinitely long lists).<br />
<br />
== Weak Head Normal Form ==<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
People who understand seq and weak head normal form (whnf) can immediately understand what goes wrong here. <hask>(acc+x, len+1)</hask> is already in whnf, so <hask>seq</hask>, which reduces a value to whnf, does nothing to this. This code will build up thunks just like the original <hask>foldl</hask> example, they'll just be inside a tuple. The solution is just to force the components of the tuple, e.g.<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)<br />
</haskell><br />
or more clearly and concisely using a recent GHC extension<br />
<haskell><br />
myAverage = uncurry (/) . foldl' (\(!acc, !len) x -> (acc+x, len+1)) (0,0)<br />
</haskell><br />
<br />
== Scans ==<br />
<br />
A subtle stack-overflow surprise comes when<br />
<haskell><br />
print (scanl (+) 0 [1..1000000])<br />
</haskell><br />
completes successfully but<br />
<haskell><br />
print (last (scanl (+) 0 [1..1000000]))<br />
</haskell><br />
causes a stack overflow.<br />
<br />
The latter stack overflow is explained exactly as before, namely,<br />
<haskell><br />
last (scanl (+) 0 [1..5]) -><br />
<nowiki>... several steps ...</nowiki> -><br />
((((0+1)+2)+3)+4)+5<br />
</haskell><br />
This is exactly like <hask>foldl</hask>, building a deep thunk, then evaluating, needing much stack.<br />
<br />
Most puzzling is why the former succeeds without a stack overflow. This is caused by a combination of two factors:<br />
* thunks in the list produced by <hask>scanl</hask> enjoy sharing: late thunks build upon early thunks<br />
* printing a list of numbers evaluates early thunks and then late thunks<br />
To exemplify, here is an abridged progression. I use this pseudo format to depict sharing of thunks<br />
<haskell><br />
expr where var=expr, var=expr<br />
</haskell><br />
although in reality it is more like a pointer graph.<br />
<haskell><br />
print (scanl (+) 0 [1..1000000]) -><br />
print (a : case [1..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (a+x) xs) where a=0 -><br />
<nowiki>... evaluate a to 0 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (a+1) [2..1000000]) where a=0 -><br />
print (b : case [2..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (b+x) xs) where a=0, b=a+1 -><br />
<nowiki>... evaluate b to 1 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (b+2) [3..1000000]) where b=1 -><br />
print (c : case [3..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (c+x) xs) where b=1, c=b+2 -><br />
<nowiki>... evaluate c to 3 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (c+3) [4..1000000]) where c=3 -><br />
print (d : case [4..1000000] of <nowiki>...</nowiki> x:xs -> scanl (+) (d+x) xs) where c=3, d=c+3 -><br />
<nowiki>... evaluate d to 6 for printing, I/O, some more steps ...</nowiki> -><br />
<br />
print (scanl (+) (d+4) [5..1000000]) where d=6 -> etc.<br />
</haskell><br />
The important thing to watch is the life cycle of intermediate thunks, e.g., <hask>c</hask> is created at some point as a 1-level deep addition, then almost immediately reduced to a number out of necessity, before a later thunk <hask>d</hask> builds upon it. Therefore there is no growth and no stack overflow.<br />
<br />
In contrast, again, <hask>last (scanl (+) 0 [1..1000000])</hask> skips over to the last thunk right away. Since early items are not reduced yet, the last item remains a huge chain and causes overflow.<br />
<br />
As an addendum, there are three ways of handling this problem and similar ones:<br />
# You can have your traversal functions (in this case, last) force the list as it goes along.<br />
# You can use (perhaps custom) versions of the list (or data structure, in general) producing functions (in this case, scanl) that force the elements as it builds the data structure.<br />
# You can use a data structure that's strict in its elements, in this case it would be a head strict list.</div>Drbbhttps://wiki.haskell.org/index.php?title=OpenGLTutorial2&diff=43862OpenGLTutorial22012-01-07T19:58:22Z<p>Drbb: /* Summary */ links</p>
<hr />
<div>''This tutorial [http://blog.mikael.johanssons.org/archive/2006/09/opengl-programming-in-haskell-a-tutorial-part-2/] was originally written by Mikael Vejdemo Johansson, and was copied here with permission.''<br />
<br />
As we left off the [[OpenGLTutorial1|last installment]], we were just about capable to open up a window, and draw some basic things in it by giving coordinate lists to the command renderPrimitive. The programs we built suffered under a couple of very infringing and ugly restraints when we wrote them - for one, they weren't really very modularized. The code would have been much clearer had we farmed out important subtasks on other modules. For another, we never even considered the fact that some manipulations would not necessarily be good to do on the entire picture.<br />
<br />
==Some modules==<br />
To deal with the first problem, let's break apart our program a little bit, forming several more or less independent code files linked together to form a whole.<br />
<br />
First off, HelloWorld.hs - containing a very generic program skeleton. We will use our module Bindings to setup everything else we might need, and tie them to the callbacks.<br />
<haskell><br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Bindings<br />
main = do<br />
(progname,_) <- getArgsAndInitialize<br />
createWindow "Hello World"<br />
displayCallback $= display<br />
reshapeCallback $= Just reshape<br />
keyboardMouseCallback $= Just keyboardMouse<br />
mainLoop<br />
</haskell><br />
Then Bindings.hs - our switchboard<br />
<haskell><br />
module Bindings (display,reshape,keyboardMouse) where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Display<br />
reshape s@(Size w h) = do <br />
viewport $= (Position 0 0, s)<br />
keyboardMouse key state modifiers position = return ()<br />
</haskell><br />
<br />
We're going to be hacking around a LOT with the display function, so let's isolate that one to a module of its own: Display.hs<br />
<haskell><br />
module Display (display) where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Cube<br />
display = do <br />
clear [ColorBuffer]<br />
cube (0.2::GLfloat)<br />
flush<br />
</haskell><br />
And a first utility module, containing the gritty details of drawing the cube <math>[-w,w]^3</math>, called Cube.hs<br />
<haskell><br />
module Cube where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
cube w = do <br />
renderPrimitive Quads $ do<br />
vertex $ Vertex3 w w w<br />
vertex $ Vertex3 w w (-w)<br />
vertex $ Vertex3 w (-w) (-w)<br />
vertex $ Vertex3 w (-w) w<br />
vertex $ Vertex3 w w w<br />
vertex $ Vertex3 w w (-w)<br />
vertex $ Vertex3 (-w) w (-w)<br />
vertex $ Vertex3 (-w) w w<br />
vertex $ Vertex3 w w w<br />
vertex $ Vertex3 w (-w) w<br />
vertex $ Vertex3 (-w) (-w) w<br />
vertex $ Vertex3 (-w) w w<br />
vertex $ Vertex3 (-w) w w<br />
vertex $ Vertex3 (-w) w (-w)<br />
vertex $ Vertex3 (-w) (-w) (-w)<br />
vertex $ Vertex3 (-w) (-w) w<br />
vertex $ Vertex3 w (-w) w<br />
vertex $ Vertex3 w (-w) (-w)<br />
vertex $ Vertex3 (-w) (-w) (-w)<br />
vertex $ Vertex3 (-w) (-w) w<br />
vertex $ Vertex3 w w (-w)<br />
vertex $ Vertex3 w (-w) (-w)<br />
vertex $ Vertex3 (-w) (-w) (-w)<br />
vertex $ Vertex3 (-w) w (-w)<br />
</haskell><br />
Now, compiling this entire section with the command <hask>ghc –make -package GLUT HelloWorld.hs -o HelloWorld</hask> compiles and links each module needed, and produces, in the end, an executable to be used. There we go! Much more modularized, much smaller and simpler bits and pieces. And - an added boon - we won't normally need to recompile as much for each change we do.<br />
<br />
This skeletal program will look like:<br />
<br />
[[image:OG-Skeleton.png]]<br />
<br />
==Local transformations==<br />
One of the core reasons I started to write this tutorial series was that I wanted to figure out why [http://www.tfh-berlin.de/~panitz/hopengl/skript.html Panitz' tutorial] didn't work for me. The core explanation is simple - the names of some of the functions used has changed since he wrote them. Thus, the matrixExcursion in his tutorial is nowadays named preservingMatrix. This may well change further - though I hope it won't - in which case this tutorial will be painfully out of date as well.<br />
<br />
The idea of preservingMatrix, however, is to take a small piece of drawing actions, and perform them independent of the transformations going on outside that small piece. For demonstration, let's draw a bunch of cubes, shall we?<br />
<br />
We'll change the rather boring display subroutine in Display.hs into one using preservingMatrix to modify each cube drawn individually, giving a new Display.hs:<br />
<haskell><br />
module Display (display) where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Cube<br />
points :: [(GLfloat,GLfloat,GLfloat)]<br />
points = map (\k -> (sin(2*pi*k/12),cos(2*pi*k/12),0.0)) [1..12]<br />
display = do <br />
clear [ColorBuffer]<br />
mapM_ (\(x,y,z) -> preservingMatrix $ do<br />
color $ Color3 x y z<br />
translate $ Vector3 x y z<br />
cube (0.1::GLfloat)<br />
) points<br />
flush<br />
</haskell><br />
Say... Those points on the unit circle might be something we'll want more of. Let's abstract some again! We'll break them out to a Points.hs. We'll have to juggle a bit with the typesystem to get things to work out, and in the end we get<br />
<haskell><br />
module Points where<br />
import Graphics.Rendering.OpenGL<br />
points :: Int -> [(GLfloat,GLfloat,GLfloat)]<br />
points n' = let n = fromIntegral n' in map (\k -> let t = 2*pi*k/n in (sin(t),cos(t),0.0)) [1..n]<br />
</haskell><br />
and then we get the Display.hs<br />
<haskell><br />
module Display (display) where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Cube<br />
import Points<br />
display = do <br />
clear [ColorBuffer]<br />
mapM_ (\(x,y,z) -> preservingMatrix $ do<br />
color $ Color3 ((x+1.0)/2.0) ((y+1.0)/2.0) ((z+1.0)/2.0)<br />
translate $ Vector3 x y z<br />
cube (0.1::GLfloat)<br />
) $ points 7<br />
flush<br />
</haskell><br />
where we note that we need to renormalize our colours to get them within the interval [0,1] from the interval [-1,1] in order to get valid colour values. The program looks like<br />
<br />
[[image:OG-7circle.png]]<br />
<br />
The point of this yoga doesn't come apparent until you start adding some global transformations as well. So let's! We add the line<br />
<br />
<haskell>scale 0.7 0.7 (0.7::GLfloat)</haskell><br />
<br />
just after the <hask>clear [ColorBuffer]</hask>, in order to scale the entire picture. As a result, we get<br />
<br />
[[image:OG-7circlescaled.png]]<br />
<br />
We can do this with all sorts of transformations - we can rotate the picture, skew it, move the entire picture around. Using preservingMatrix, we make sure that the transformations “outside” apply in the way we'd expect them to.<br />
<br />
==Back to the callbacks==<br />
===Animation===<br />
A lot of the OpenGL programming is centered around the program being prepared to launch some sequence when some event occurs. Let's use this to build a rotating version of our bunch of points up there. In order to do things over time, we're going to be using the global callbacks idleCallback and timerCallback. So, we'll modify the structure of our files a bit - starting from the top.<br />
<br />
We'll need a new callback. And we'll also need a state variable of our own, which in turn needs to be fed to all functions that may need to use it. Incorporating these changes, we get a new HelloWorld.hs:<br />
<haskell><br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Bindings<br />
import Data.IORef<br />
main = do<br />
(progname,_) <- getArgsAndInitialize<br />
createWindow "Hello World"<br />
reshapeCallback $= Just reshape<br />
keyboardMouseCallback $= Just keyboardMouse<br />
angle <- newIORef 0.0<br />
displayCallback $= (display angle)<br />
idleCallback $= Just (idle angle)<br />
mainLoop<br />
</haskell><br />
Note the addition of an angle, and an idle. We need to feed the value of angle both to idle and to display, in order for them to use it accordingly. Now, we need to define idle somewhere - and since we keep all the bits and pieces we modify a LOT in display, let's put it in there.<br />
<br />
Exporting it all the way requires us to change the first line of Bindings.hs to<br />
<haskell>module Bindings (idle,display,reshape,keyboardMouse) where</haskell><br />
<br />
Display.hs:<br />
<haskell><br />
module Display (display,idle) where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Data.IORef<br />
import Cube<br />
import Points<br />
display angle = do <br />
clear [ColorBuffer]<br />
a <- get angle<br />
rotate a $ Vector3 0 0 (1::GLfloat)<br />
scale 0.7 0.7 (0.7::GLfloat)<br />
mapM_ (\(x,y,z) -> preservingMatrix $ do<br />
color $ Color3 ((x+1.0)/2.0) ((y+1.0)/2.0) ((z+1.0)/2.0)<br />
translate $ Vector3 x y z<br />
cube (0.1::GLfloat)<br />
) $ points 7<br />
flush<br />
idle angle = do<br />
a <- get angle<br />
angle $=! a + 0.1<br />
postRedisplay Nothing -- Only required on Mac OS X, which double-buffers internally<br />
</haskell><br />
<br />
Now, running this program makes a couple of different things painfully obvious. One is that things flicker. (Note: Mac OS X double-buffers internally so it does not flicker). Another is that our ring is shrinking violently. The shrinking is due to our forgetting to reset all our transformations before we apply the next, and the flicker is because we're redrawing an entire picture step by step. Much smoother animation'll be had if we use a double buffering technique. Now, this isn't at all hard. We need to modify a few places - tell HOpenGL that we want to do doublebuffering and also when we want to swap the ready drawn canvas for the one on the screen. So, we modify, again, HelloWorld.hs:<br />
<br />
<haskell><br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Data.IORef<br />
import Bindings<br />
main = do<br />
(progname,_) <- getArgsAndInitialize<br />
initialDisplayMode $= [DoubleBuffered]<br />
createWindow "Hello World"<br />
reshapeCallback $= Just reshape<br />
keyboardMouseCallback $= Just keyboardMouse<br />
angle <- newIORef 0.0<br />
idleCallback $= Just (idle angle)<br />
displayCallback $= (display angle)<br />
mainLoop<br />
</haskell><br />
and we also need to modify Display.hs to implement the bufferswapping. While we're at it, we add the command loadIdentity, which resets the modification matrix.<br />
<haskell><br />
module Display (display,idle) where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Data.IORef<br />
import Cube<br />
import Points<br />
display angle = do <br />
clear [ColorBuffer]<br />
loadIdentity<br />
a <- get angle<br />
rotate a $ Vector3 0 0 (1::GLfloat)<br />
scale 0.7 0.7 (0.7::GLfloat)<br />
mapM_ (\(x,y,z) -> preservingMatrix $ do<br />
color $ Color3 ((x+1.0)/2.0) ((y+1.0)/2.0) ((z+1.0)/2.0)<br />
translate $ Vector3 x y z<br />
cube (0.1::GLfloat)<br />
) $ points 7<br />
swapBuffers<br />
idle angle = do<br />
a <- get angle<br />
angle $=! a+0.1<br />
postRedisplay Nothing<br />
</haskell><br />
<br />
There we are! That looks pretty, doesn't it? Now, we could start adding control to the user, couldn't we? Let's add some keyboard interfaces. We'll start by letting the rotation direction change when we press spacebar, and let the arrows displace the whole figure and + and - increase/decrease the rotation speed.<br />
Again, we're adding states, so we need to modify HelloWorld.hs<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Data.IORef<br />
import Bindings<br />
main = do<br />
(progname,_) <- getArgsAndInitialize<br />
initialDisplayMode $= [DoubleBuffered]<br />
createWindow "Hello World"<br />
reshapeCallback $= Just reshape<br />
angle <- newIORef (0.0::GLfloat)<br />
delta <- newIORef (0.1::GLfloat)<br />
position <- newIORef (0.0::GLfloat, 0.0)<br />
keyboardMouseCallback $= Just (keyboardMouse delta position)<br />
idleCallback $= Just (idle angle delta)<br />
displayCallback $= (display angle position)<br />
mainLoop<br />
<br />
Note that position is sent along to the keyboard as well as the display callbacks. And in Bindings.hs, we give the keyboard callback actual function<br />
<haskell><br />
module Bindings (idle,display,reshape,keyboardMouse) where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Data.IORef<br />
import Display<br />
reshape s@(Size w h) = do <br />
viewport $= (Position 0 0, s)<br />
keyboardAct a p (Char ' ') Down = do<br />
a' <- get a<br />
a $= -a'<br />
keyboardAct a p (Char '+') Down = do<br />
a' <- get a<br />
a $= 2*a'<br />
keyboardAct a p (Char '-') Down = do<br />
a' <- get a<br />
a $= a'/2<br />
keyboardAct a p (SpecialKey KeyLeft) Down = do<br />
(x,y) <- get p<br />
p $= (x-0.1,y)<br />
keyboardAct a p (SpecialKey KeyRight) Down = do<br />
(x,y) <- get p<br />
p $= (x+0.1,y)<br />
keyboardAct a p(SpecialKey KeyUp) Down = do<br />
(x,y) <- get p<br />
p $= (x,y+0.1)<br />
keyboardAct a p (SpecialKey KeyDown) Down = do<br />
(x,y) <- get p<br />
p $= (x,y-0.1)<br />
keyboardAct _ _ _ _ = return ()<br />
keyboardMouse angle pos key state modifiers position = do<br />
keyboardAct angle pos key state<br />
</haskell><br />
<br />
finally, in Display.hs we use the new information to accordingly redraw the scene, specifically the now changing amount to change the current angle with. Note that in order to avoid the placement of the circle to be pulled in with all the other modifications we're doing, we do the translation outside a preservingMatrix call.<br />
<br />
<haskell><br />
module Display (display,idle) where<br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
import Data.IORef<br />
import Cube<br />
import Points<br />
display angle position = do <br />
clear [ColorBuffer]<br />
loadIdentity<br />
(x,y) <- get position<br />
translate $ Vector3 x y 0<br />
preservingMatrix $ do <br />
a <- get angle<br />
rotate a $ Vector3 0 0 (1::GLfloat)<br />
scale 0.7 0.7 (0.7::GLfloat)<br />
mapM_ (\(x,y,z) -> preservingMatrix $ do<br />
color $ Color3 ((x+1.0)/2.0) ((y+1.0)/2.0) ((z+1.0)/2.0)<br />
translate $ Vector3 x y z<br />
cube (0.1::GLfloat)<br />
) $ points 7<br />
swapBuffers<br />
idle angle delta = do<br />
a <- get angle<br />
d <- get delta<br />
angle $=! a+d<br />
postRedisplay Nothing<br />
</haskell><br />
<br />
==Summary==<br />
We now know how to modify only parts of a picture, and we also know how to use the idle and the keyboardMouse callback to support animations and keyboard input.<br />
<br />
In order to somewhat limit the amount of typing I need to do, I'll give links that give details on some of the themes we've touched upon.<br />
<br />
First of all, the callbacks are described in more detail and with call signatures at<br />
[http://lambda.haskell.org/platform/doc/2011.4.0.0/packages/GLUT-2.1.2.1/doc/html/Graphics-UI-GLUT-Callbacks-Global.html Graphics.UI.GLUT.Callbacks.Global] for the global callbacks (menu systems, and timing/idle callbacks)<br />
<br />
[http://lambda.haskell.org/platform/doc/2011.4.0.0/packages/GLUT-2.1.2.1/doc/html/Graphics-UI-GLUT-Callbacks-Window.html Graphics.UI.GLUT.Callbacks.Window] for the window-specific callbacks (display, reshape, keyboard&mouse, visibility changes, window closing, mouse movement, spaceballs, drawing tablets, joysticks and dial&button)<br />
<br />
Furthermore, the various primitives for drawing are listed at [http://lambda.haskell.org/platform/doc/2011.4.0.0/packages/OpenGL-2.2.3.0/doc/html/Graphics-Rendering-OpenGL-GL-BeginEnd.html Graphics.Rendering.OpenGL.GL.BeginEnd].<br />
<br />
There are 3-dimensional primitives ready as well. These can be found at [http://lambda.haskell.org/platform/doc/2011.4.0.0/packages/GLUT-2.1.2.1/doc/html/Graphics-UI-GLUT-Objects.html Graphics.UI.GLUT.Objects]<br />
<br />
The flag I set to trigger double buffering is described among the GLUT initialization methods, see [http://lambda.haskell.org/platform/doc/2011.4.0.0/packages/GLUT-2.1.2.1/doc/html/Graphics-UI-GLUT-Initialization.html Graphics.UI.GLUT.Initialization] for everything you can do there.</div>Drbbhttps://wiki.haskell.org/index.php?title=OpenGLTutorial1&diff=43861OpenGLTutorial12012-01-07T19:49:39Z<p>Drbb: /* Hello World */ fixed Mac-compatibility, and clarified presentation (I hope)</p>
<hr />
<div>''This tutorial [http://blog.mikael.johanssons.org/archive/2006/09/opengl-programming-in-haskell-a-tutorial-part-1/] was originally written by Mikael Vejdemo Johansson, and was copied here with permission.''<br />
<br />
After having failed following the [http://www.cs.hs-rm.de/~panitz/hopengl/skript.html googled tutorial in HOpenGL programming], I thought I'd write down the steps I actually can get to work in a tutorial-like fashion. It may be a good idea to read this in parallell to the tutorial linked, since Panitz actually brings a lot of good explanations, even though his syntax isn't up to speed with the latest HOpenGL at all points.<br />
<br />
Note: GHCI interactive shell has problems running these program on some platforms (such as Mac OS X). <strong>Vompile these programs with ghc, and run the generated executables.<br />
</strong><br />
<br />
==Hello World==<br />
First of all, we'll want to load the OpenGL libraries, throw up a window, and generally get to grips with what needs to be done to get a program running at all. <br />
<br />
<haskell><br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
<br />
main :: IO ()<br />
main = do <br />
(progname, _) <- getArgsAndInitialize<br />
createWindow "Hello World"<br />
displayCallback $= flush<br />
mainLoop<br />
</haskell><br />
<br />
This code throws up a window, with a given title, and sets the main display function to do nothing but flush the (empty) graphics buffer. This is the skeleton that we'll be building on to.<br />
<br />
Save it to HelloWorld.hs and compile it by running <hask>ghc -package GLUT HelloWorld.hs -o HelloWorld</hask>.<br />
<br />
You will see a window open, with titled "Hellow World", with either a blank canvas, or with some garbage graphics content pulled from somewhere in your system's graphics memory.<br />
<br />
In either case, this program is profoundly worthless.<br />
<br />
At a minimum, let's have our program display a clean blank canvas:<br />
<br />
So we modify our code to the following:<br />
<br />
<haskell><br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
<br />
main :: IO ()<br />
main = do<br />
(progname, _) <- getArgsAndInitialize<br />
createWindow "Hello World"<br />
displayCallback $= display<br />
mainLoop<br />
<br />
display :: IO ()<br />
display = do<br />
clear [ ColorBuffer ]; flush<br />
<br />
</haskell><br />
<br />
This defines a function "display" that calls a few OpenGL functions: "clear" to clear out the graphics color state (so we get a blank canvas), and "flush" to push our OpenGL commands down to the system graphics for actual display.<br />
<br />
We don't call "display" directly. (In fact, we don't call any graphics drawing functions directly). Instead, we set a display callback, and then call mainLoop. In mainLoop, OpenGL akes over, handles all the details of interacting with the OS and refreshing our window, calling our displayCallback to draw graphics.<br />
<br />
displayCallback is a Data.IORef (mutable state variable), which we set using a call to <hask>($=)</hask>.<br />
<br />
Save this to the HelloWorld.hs, recompile, and rerun. This program displays an endless series of blank canvases (a solid blank image).<br />
<br />
The displayCallback is a globally defined IORef, which can be accessed through a host of functions defined in Data.IORef. In [http://hackage.haskell.org/packages/archive/OpenGL/2.2.2.0/doc/html/Graphics-Rendering-OpenGL-GL-StateVar.html OpenGL StateVar module], there is a HasSetter type class and an IORef implementation providing functions <hask>($=)</hask> (assignment) and <hask>get</hask> to fascilitate interactions with these state variables. <br />
<br />
<haskell><br />
height = newIORef 1.0<br />
currentheight <- get height<br />
height $= 1.5<br />
</haskell><br />
<br />
==Using the drawing canvas==<br />
So, we have a window, we have a display callback that clears the canvas. Don't we want more out of it? Sure we do. So let's draw some things.<br />
<haskell><br />
import Graphics.Rendering.OpenGL<br />
import Graphics.UI.GLUT<br />
myPoints :: [(GLfloat,GLfloat,GLfloat)]<br />
myPoints = map (\k -> (sin(2*pi*k/12),cos(2*pi*k/12),0.0)) [1..12]<br />
main = do <br />
(progname, _) <- getArgsAndInitialize<br />
createWindow "Hello World"<br />
displayCallback $= display<br />
mainLoop<br />
display = do <br />
clear [ColorBuffer]<br />
renderPrimitive Points $ mapM_ (\(x, y, z)->vertex$Vertex3 x y z) myPoints<br />
flush<br />
</haskell><br />
<br />
Now, the important thing to notice in this codeextract is that last line. It starts a rendering definition, gives the type to be rendered, and then a sequence of function calls, each of which adds a vertex to the rendering canvas. The statement is basically equivalent to something along the lines of<br />
<haskell><br />
renderPrimitive Points do<br />
vertex Vertex3 ...<br />
vertex Vertex3 ...<br />
</haskell><br />
for appropriate triples of coordinate values at the appropriate places. This results in the rendition here:<br />
<br />
[[image:OG-Points.png]]<br />
<br />
We can replace Points with other primitives, leading to the rendering of:<br />
<br />
===Triangles===<br />
[[image:OG-Triangles.png]]<br />
<br />
Each three coordinates following each other define a triangle. The last n mod 3 coordinates are ignored.<br />
<br />
Keyword Triangles<br />
<br />
===Triangle strips===<br />
[[image:OG-Trianglestrip.png]]<br />
<br />
Triangles are drawn according to a “moving window” of size three, so the two last coordinates in the previous triangle become the two first in the next triangle.<br />
<br />
Keyword TriangleStrip<br />
<br />
===Triangle fans===<br />
[[image:OG-Trianglesfan.png]]<br />
<br />
Triangle fans have the first given coordinate as a basepoint, and takes each pair of subsequent coordinates to define a triangle together with the first coordinate.<br />
<br />
Keyword TriangleFan<br />
<br />
===Lines===<br />
[[image:OG-Lines.png]]<br />
<br />
Each pair of coordinates define a line.<br />
<br />
Keyword Lines<br />
<br />
===Line loops===<br />
[[image:OG-Lineloop.png]]<br />
<br />
With line loops, each further coordinate defines a line together with the last coordinate used. Once all coordinates are used up, an additional line is drawn back to the beginning.<br />
<br />
Keyword LineLoop<br />
<br />
===Line strips===<br />
[[image:OG-Linestrip.png]]<br />
<br />
Line strips are like line loops, only without the last link added.<br />
<br />
Keyword LineStrip<br />
<br />
===Quadrangles===<br />
[[image:OG-Quad.png]]<br />
<br />
For the Quads keyword, each four coordinates given define a quadrangle.<br />
<br />
Keyword Quads<br />
<br />
===Quadrangle strips===<br />
[[image:OG-Quadstrip.png]]<br />
<br />
And a Quadstrip works as the trianglestrip, only the window is 4 coordinates wide and steps 2 steps each time, so each new pair of coordinates attaches a new quadrangle to the last edge of the last quadrangle.<br />
<br />
Keyword QuadStrip<br />
<br />
===Polygon===<br />
[[image:OG-Polygon.png]]<br />
<br />
A Polygon is a filled line loop. Simple as that!<br />
<br />
Keyword Polygon<br />
<br />
There are more things we can do on our canvas than just spreading out coordinates. Within the command list constructed after a renderPrimitive, we can give several different commands that control what things are supposed to look like, so for instance we could use the following:<br />
<haskell><br />
display = do <br />
clear [ColorBuffer]<br />
renderPrimitive Quads $ do<br />
color $ (Color3 (1.0::GLfloat) 0 0)<br />
vertex $ (Vertex3 (0::GLfloat) 0 0)<br />
vertex $ (Vertex3 (0::GLfloat) 0.2 0)<br />
vertex $ (Vertex3 (0.2::GLfloat) 0.2 0)<br />
vertex $ (Vertex3 (0.2::GLfloat) 0 0)<br />
color $ (Color3 (0::GLfloat) 1 0)<br />
vertex $ (Vertex3 (0::GLfloat) 0 0)<br />
vertex $ (Vertex3 (0::GLfloat) (-0.2) 0)<br />
vertex $ (Vertex3 (0.2::GLfloat) (-0.2) 0)<br />
vertex $ (Vertex3 (0.2::GLfloat) 0 0)<br />
color $ (Color3 (0::GLfloat) 0 1)<br />
vertex $ (Vertex3 (0::GLfloat) 0 0)<br />
vertex $ (Vertex3 (0::GLfloat) (-0.2) 0)<br />
vertex $ (Vertex3 ((-0.2)::GLfloat) (-0.2) 0)<br />
vertex $ (Vertex3 ((-0.2)::GLfloat) 0 0)<br />
color $ (Color3 (1::GLfloat) 0 1)<br />
vertex $ (Vertex3 (0::GLfloat) 0 0)<br />
vertex $ (Vertex3 (0::GLfloat) 0.2 0)<br />
vertex $ (Vertex3 ((-0.2::GLfloat)) 0.2 0)<br />
vertex $ (Vertex3 ((-0.2::GLfloat)) 0 0)<br />
flush<br />
</haskell><br />
in order to produce these four coloured squares:<br />
<br />
[[image:OG-Colorsquares.png]]<br />
<br />
where each color command sets the color for the next item drawn, and the vertex commands give vertices for the four squares.<br />
<br />
==Callbacks - how we react to changes==<br />
We have already seen one callback in action: displayCallBack. The Callbacks are state variables of the HOpenGL system, and are called in order to handle various things that may happen to the place the drawing canvas lives. For a first exercise, go resize the latest window you've used. Go on, do it now.<br />
<br />
I bet it looked ugly, didn't it?<br />
<br />
This is because we have no code handling what to do if the window should suddenly change. Handling this is done in a callback, residing in the IORef reshapeCallback. Similarily, repainting is done in displayCallback, keyboard and mouse input is in keyboardMouseCallback, and so on. We can refer to the HOpenGL documentation for [http://hackage.haskell.org/packages/archive/GLUT/latest/doc/html/Graphics-UI-GLUT-Callbacks-Window.html window callbacks] and for [http://hackage.haskell.org/packages/archive/GLUT/latest/doc/html/Graphics-UI-GLUT-Callbacks-Global.html global callbacks]. Window callbacks are things like display, keyboard and mouse, and reshape. Global callbacks deal with timing issues (for those snazzy animations) and the menu interface systems.<br />
<br />
In order for a callback to possibly not be defined, most are typed within the Maybe monad, so by setting the state variable to Nothing, a callback can be disabled. Thus, setting callbacks is done using the keyword Just. We'll add a callback for reshaping the window to our neat code, changing the main function to:<br />
<haskell><br />
main = do <br />
(progname, _) <- getArgsAndInitialize<br />
createWindow "Hello World"<br />
displayCallback $= display<br />
reshapeCallback $= Just reshape<br />
mainLoop<br />
reshape s@(Size w h) = do<br />
viewport $= (Position 0 0, s)<br />
postRedisplay Nothing<br />
</haskell><br />
<br />
Here, the code for the reshape function resizes the viewport so that our drawing area contains the entire new window. After setting the new viewport, it also tells the windowing system that something has happened to the window, and that therefore, the display function should be called.<br />
<br />
==Summary==<br />
So, in conclusion, so far we can display a window, post basic callbacks to get the windowhandling to run smoothly, and draw in our window. Next installment of the tutorial will bring you 3d drawing, keyboard and mouse interactions, the incredible power of matrices and the ability to rotate 3d objects for your leisure. Possibly, we'll even look into animations.<br />
<br />
[[OpenGLTutorial2|Continue with part 2]]</div>Drbbhttps://wiki.haskell.org/index.php?title=Books&diff=43844Books2012-01-06T05:57:10Z<p>Drbb: /* =. Foreword of the book (en) */</p>
<hr />
<div>Books covering many aspects of Haskell.<br />
<br />
==Language and library definition==<br />
<br />
<DL><br />
<DT>[[Image:Haskell_98_Language_and_Libraries.jpg|Cover]]<br />
Simon Peyton Jones: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521826144 "Haskell 98 language and libraries: the Revised Report"], Cambridge University Press, 2003, Hardback, 272 pages, ISBN 0521826144, £45.00<br />
<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
Haskell is the world's leading lazy functional programming language,<br />
widely used for teaching, research, and applications. The language<br />
continues to develop rapidly, but in 1998 the community decided to<br />
capture a stable snapshot of the language: Haskell 98. All Haskell<br />
compilers support Haskell 98, so practitioners and educators alike<br />
have a stable base for their work. This book constitutes the agreed<br />
definition of the Haskell 98, both the language itself and its<br />
supporting libraries. It has been considerably revised and refined<br />
since the original definition, and appears in print for the first<br />
time. It should be a standard reference work for anyone involved in<br />
research, teaching, or application of Haskell.<br />
</BLOCKQUOTE> <br />
The entire language definition is also available online:<br />
[[Language_and_library_specification|Language and library<br />
specification]].<br />
</DL><br />
<br />
==Textbooks==<br />
<br />
<DL><br />
<br />
<dt>[[Image:Lyah.png|Cover]] Miran Lipovača: [http://www.nostarch.com/lyah.htm <em>Learn You a Haskell for Great Good!</em>], Paperback: 360 pages, No Starch Press (April 2011), English, ISBN: 978-1-59327-283-8<br />
<blockquote><br />
<B>Book Description</B><BR><br />
It's all in the name: Learn You a Haskell for Great Good! is a hilarious, illustrated guide to this complex functional language. Packed with the author's original artwork, pop culture references, and most importantly, useful example code, this book teaches functional fundamentals in a way you never thought possible.<br />
</blockquote><br />
<br />
<dt>[[Image:Programming_in_Haskell.jpg|Cover]] Graham Hutton: [http://www.cs.nott.ac.uk/~gmh/book.html <em>Programming in Haskell</em>], Paperback: 200 pages, Cambridge University Press (January 31, 2007), English, ISBN 0521692695<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
Haskell is one of the leading languages for teaching functional<br />
programming, enabling students to write simpler and cleaner code, and to<br />
learn how to structure and reason about programs. This introduction is<br />
ideal for beginners: it requires no previous programming experience and<br />
all concepts are explained from first principles via carefully chosen<br />
examples. Each chapter includes exercises that range from the<br />
straightforward to extended projects, plus suggestions for further<br />
reading on more advanced topics. The author is a leading Haskell<br />
researcher and instructor, well-known for his teaching skills. The<br />
presentation is clear and simple, and benefits from having been refined<br />
and class-tested over several years. The result is a text that can be<br />
used with courses, or for self-learning. Features include: freely<br />
accessible Powerpoint slides for each chapter; solutions to exercises,<br />
and examination questions (with solutions) available to instructors;<br />
downloadable code that's fully compliant with the latest Haskell<br />
release.<br />
</blockquote><br />
<br />
<dt>[[Image:Rwh-thumb.png|Cover]] Bryan O'Sullivan, Don Stewart, and John Goerzen: [http://book.realworldhaskell.org/ <em>Real World Haskell</em>], Paperback: 700 pages, O'Reilly, November 2008, English, ISBN-10: 0596514980, ISBN-13: 978-0596514983<br />
<blockquote><br />
See ''[[Real World Haskell]]''. <br />
</blockquote><br />
<br />
<DT>[[Image:The_Haskell_School_of_Expression.jpg|Cover]] Paul Hudak: [http://plucky.cs.yale.edu/soe <EM>The Haskell School of Expression: Learning Functional Programming through Multimedia</EM>], Cambridge University Press, New York, 2000, 416<br />
pp, 15 line diagrams, 75 exercises, Paperback $29.95, ISBN 0521644089, Hardback $74.95, ISBN 0521643384<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
This book teaches functional programming as a way of thinking and<br />
problem solving, using Haskell, the most popular purely functional<br />
language. Rather than using the conventional mathematical examples<br />
commonly found in other programming language textbooks, the author<br />
draws examples from multimedia applications, including graphics,<br />
animation, and computer music, thus rewarding the reader with working<br />
programs for inherently more interesting applications. Aimed at both<br />
beginning and advanced programmers, this tutorial begins with a gentle<br />
introduction to functional programming and moves rapidly on to more<br />
advanced topics. An underlying theme is the design and implementation<br />
of <em>domain specific languages</em>, using three examples: FAL (a Functional<br />
Animation Language), IRL (an Imperative Robot Language), and MDL (a<br />
Music Description Language). Details about programming in Haskell<br />
are presented in boxes throughout the text so they can be easily<br />
referred to and found quickly.<br />
<br />
The book's [http://plucky.cs.yale.edu/soe Web Site] contains source files for all programs in the text, as well as the graphics libraries to run them under Windows and Linux platforms. It also contains PowerPoint slides useful for<br />
teaching a course using the textbook.<br />
<br />
*There is a review of SOE on this wiki: [[The Monad.Reader/Issue3/SoE Review]].<br />
</blockquote><br />
<DT>[[Image:The_Craft_of_Functional_Programming.jpg|Cover]] Simon Thompson: [http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/ <EM>Haskell: The Craft of Functional Programming</EM>], Second Edition,<br />
Addison-Wesley, 507&nbsp;pages, paperback, 1999. ISBN 0-201-34275-8.<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
The second edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice an program design, testing, problem solving and how to avoid common pitfalls. <br />
<br />
Building on the strengths of the first edition, the book includes many new and improved features: <br />
*Complete coverage of Haskell 98, the standard version of Haskell which will be stable and supported by implementations for years to come. <br />
*An emphasis on software engineering principles, encouraging a disciplined approach to building reusable libraries of software components. <br />
*Detailed coverage of the Hugs interpreter with an appendix covering other implementations. <br />
*A running case study of pictures emphasizes the built-in functions which appear in the standard prelude and libraries. It is also used to give an early preview of some of the more complex language features, such as high-order functions. <br />
*List comprehensions and the standard functions over lists are covered before recursion. <br />
*Early coverage of polymorphism supporting the "toolkit" approach and encouraging the resuse of built-in functions and types. <br />
*Extensive reference material containing details of further reading in books, journals and on the World Wide Web. <br />
*Accompanying Web Site supporting the book, containing all the program code, further teaching materials and other useful resources. <br />
<B>Synopsis</B><BR> <br />
This books introduces Haskell at a level appropriate for those with little or no prior experience of functional programming. The emphasis is on the process of crafting programs, solving problems, and avoiding common errors.<br />
</blockquote><br />
<br />
<DT>[[Image:Introduction_to_Functional_Programming.jpg|Cover]] Richard Bird: [http://www.prenhall.com/allbooks/ptr_0134843460.html <EM>Introduction to Functional Programming using Haskell</EM>], 2nd edition, Prentice Hall Press, 1998, 460 pp., ISBN 0-13-484346-0.<br />
<blockquote><br />
From the cover:<br />
<br />
After the success of the first edition, Introduction to Functional Programming using Haskell has been thoroughly updated and revised to provide a complete grounding in the principles and techniques of programming with functions.<br />
<br />
The second edition uses the popular language Haskell to express functional programs. There are new chapters on program optimisation, abstract datatypes in a functional setting, and programming in a monadic style. There are completely new case studies, and many new exercises.<br />
<br />
As in the first edition, there is an emphasis on the fundamental techniques for reasoning about functional programs, and for deriving them systematically from their specifications.<br />
<br />
The book is self-contained, assuming no prior knowledge of programming, and is suitable as an introductory undergraduate text for first- or second-year students.<br />
</blockquote><br />
<br />
<br />
<DT>[[Image:Introduction_to_Functional_Programming_Systems_Using_Haskell.jpg|Cover]] Antony Davie: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521277248 <EM>An Introduction to Functional Programming Systems Using Haskell</EM>], Cambridge University Press, 1992. ISBN 0-521-25830-8 (hardback). ISBN 0-521-27724-8 (paperback).<br />
<blockquote><br />
Cover:<br />
<br />
Functional programming is a style of programming that has become increasingly popular during the past few years.<br />
Applicative programs have the advantage of being almost immediately expressible as functional descriptions; they can<br />
be proved correct and transformed through the referential transparency property.<br />
<br />
This book presents the basic concepts of functional programming, using the language Haskell for examples. The author<br />
incorporates a discussion of lambda calculus and its relationship with Haskell, exploring the implications for<br />
raparallelism. Contents: SASL for Beginners / Examples of SASL Programming / More Advanced Applicative Programming<br />
Techniques / Lambda Calculus / The Relationship Between Lambda Calculus and SASL / Program Transformation and<br />
Efficiency / Correctness, Equivalence and Program Verification / Landin's SECD Machine and Related<br />
Implementations / Further Implementation Techniques / Special Purpose Hardware / The Applicative Style of<br />
Semantics / Other Applicative Languages / Implications for Parallelism / Functional Programming in Von Neumann<br />
Languages <br />
</blockquote><br />
<br />
<DT>[[Image:Algorithms_A_Functional_Approach.jpg|Cover]] Fethi Rabhi and Guy Lapalme: [http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html <EM> Algorithms: A functional programming approach</EM>], <br />
Addison-Wesley, 235&nbsp;pages, paperback, 1999. ISBN 0-201-59604-0<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
The authors challenge more traditional methods of teaching algorithms<br />
by using a functional programming context, with Haskell as an<br />
implementation language. This leads to smaller, clearer and more<br />
elegant programs which enable the programmer to understand the<br />
algorithm more quickly and to use that understanding to explore<br />
alternative solutions. <br><br />
<b>Key features:</b><br />
*Most chapters are self-contained and can be taught independently from each other.<br />
*All programs are in Haskell'98 and provided on a WWW site.<br />
*End of chapter exercises throughout.<br />
*Comprehensive index and bibliographical notes.<br />
<B>Synopsis</B><BR> <br />
The book is organised as a classic algorithms book according to topics<br />
such as Abstract Data Types, sorting and searching. It uses a<br />
succession of practical programming examples to develop in the reader<br />
problem-solving skills which can be easily transferred to other<br />
language paradigms. It also introduces the idea of capturing<br />
algorithmic design strategies (e.g. Divide-and-Conquer, Dynamic<br />
Programming) through higher-order functions.<br><br />
<b>Target audience</b><br><br />
The book is intended for computer science students taking algorithms<br />
and/or (basic or advanced) functional programming courses.<br />
</BLOCKQUOTE><br />
<br />
<dt>[[Image:Fun_of_Programming.jpg|Cover]] Jeremy Gibbons and Oege de Moor (eds.): [http://www.palgrave.com/catalogue/catalogue.asp?Title_Id=0333992857 <em>The Fun of Programming</em>],Palgrave, 2002, 288 pages. ISBN 0333992857.<br />
<blockquote><br />
<b>Book description:</b><br><br />
In this textbook, leading researchers give tutorial expositions on the current state of the art of functional<br />
programming. The text is suitable for an undergraduate course immediately following an introduction to<br />
functional programming, and also for self-study. All new concepts are illustrated by plentiful examples,<br />
as well as exercises. A [http://web.comlab.ox.ac.uk/oucl/publications/books/fop/ website] gives access to accompanying software.<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones: [http://research.microsoft.com/Users/simonpj/Papers/slpj-book-1987/index.htm <em>Implementation of Functional Programming] Language</em>], 500 pages, Prentice-Hall, 1987. ISBN 0134533259.<br />
<blockquote><br />
This 1987 book is now out of print, but it is now available [http://research.microsoft.com/Users/simonpj/Papers/slpj-book-1987/index.htm online] in its entirety.<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones, David Lester: [http://www.amazon.com/Implementing-Functional-Languages-Prentice-Hall-International/dp/0137219520/sr=1-1/qid=1162002704/ref=sr_1_1/104-0009163-6568732?ie=UTF8&s=books <em>Implementing Functional Languages</em>], Paperback: 288 pages, Prentice Hall (August 1992), English, ISBN 0137219520 <br><br />
<blockquote><br />
The book is out of print. The full sources and a postscript version are <br />
[http://research.microsoft.com/Users/simonpj/Papers/papers.html available for free].<br />
<br />
This book gives a practical approach to understanding the<br />
implementations of non-strict functional languages using lazy graph<br />
reduction. The emphasis of the book is on building working prototypes of<br />
several functional language implementations (template- instantiation,<br />
G-Machine, TIM, parallel G-Machine. In each case the authors provide a<br />
complete working prototype of a particular implementation, and then lead<br />
the reader through a sequence of improvements which expand its scope.<br />
This enables readers to develop, modify and experiment with their own<br />
implementations and for use as a source of practical laboratory work<br />
material.<br />
</blockquote><br />
<br />
<dt>[[Image:TTFP.jpg|Cover]] Simon Thompson: [http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201416670/sr=1-1/qid=1162002856/ref=sr_1_1/104-0009163-6568732?ie=UTF8&s=books <em>Type Theory and Functional Programming</em>], Addison-Wesley, 1991. ISBN 0-201-41667-0. Hardcover: 388 pages.<br />
<blockquote><br />
Now out of print, the original version is available [http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ here].<br />
<br />
<em>Preface</em>:<br />
Constructive Type theory has been a topic of research interest to computer scientists,<br />
mathematicians, logicians and philosophers for a number of years. For computer scientists it provides<br />
a framework which brings together logic and programming languages in a most elegant and fertile way:<br />
program development and verification can proceed within a single system. Viewed in a different way,<br />
type theory is a functional programming language with some novel features, such as the totality of<br />
all its functions, its expressive type system allowing functions whose result type depends upon the<br />
value of its input, and sophisticated modules and abstract types whose interfaces can contain logical<br />
assertions as well as signature information. A third point of view emphasizes that programs (or<br />
functions) can be extracted from proofs in the logic.<br />
</blockquote><br />
<br />
<DT>[[Image:Uma_Abordagem_Pratica.jpg|Cover]] Claudio Cesar de Sá and Marcio Ferreira da Silva: <em> Haskell: Uma Abordagem Prática</em>, [http://www.novatec.com.br Novatec Editora Ltda.], 2006, 296 pages, ISBN 85-7522-095-0. The price is R$ 62,00 (in Reais). Language: Portuguese<br />
<blockquote><br />
This book is being published by Novatec Editora Ltda. You can access directly [http://www.novateceditora.com.br/livros/haskell/ here].<br />
<br><br />
<b>Book description:</b><br><br />
This book brings a comprehensive vision of Haskell language. No <br />
knowledge in another functional programming language is expected. In <br />
addition, no background in programming is required. The book presents <br />
issues from basic up to an intermediate level; it also includes some <br />
advanced aspects of Haskell. The title of the book, <em>Haskell: Uma <br />
Abordagem Prática</em>, in English <em>Haskell: A Practical Approach</em>, is the essence of the book.<br />
The result is a text that can be used in courses of programming and paradigms languages.<br />
Finally, many practical examples can be found <br />
throughout the book.<br />
<br />
An additional page containing comments on this book is found here:<br />
[http://www2.joinville.udesc.br/~coca/index.php/Main/PaginaDoLivroDeHaskell].<br />
Other data as bibtex entry, cover's book in several formats, <br />
Winhugs-2001 for download, and so on. This page is Portuguese.<br />
</blockquote><br />
<br />
<dt>[[Image:portada.jpg|Cover]] Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo. [http://www.lcc.uma.es/~pepeg/pfHaskell/index.html <em>Razonando con Haskell</em>], Thompson 2004. ISBN 84-9732-277-0. Language: Spanish<br />
<blockquote><br />
Descripción El objetivo principal de este libro es el de servir como<br />
libro de texto de las asignaturas de Programación Declarativa<br />
correspondientes a los estudios de Informática o Ciencias de la<br />
Computación, y otras ciencias en general ( Matemáticas, Física, etc.).<br />
El texto es fruto de una larga experiencia docente de los autores dentro<br />
de las distintas asignaturas que desarrollan la Programación Funcional<br />
en distintas titulaciones de la Universidad de Málaga. Aún así, su<br />
lectura no queda condicionada a un conocimiento previo sobre lenguajes<br />
de programación (de computadores), ni sobre Informática. De esta forma,<br />
el libro puede ser utilizado por todo aquel que desee tener un<br />
conocimiento amplio sobre la Programación Funcional. <br />
</blockquote><br />
<br />
<dt>[[Image:haskell-jp.jpg|Cover]] [http://www.amazon.co.jp/gp/product/4839919623 Haskell Primer: The first functional language to learn]. Jun Mukai. In Japanese. Yen 2,730.<br />
<blockquote><br />
</blockquote><br />
<br />
<dt>[[Image:Haskell-jp-2.jpg|Cover]] [http://www.amazon.co.jp/gp/product/4797336021 Practical Haskell Programming], Minero Aoki and Nobuo Yamashita. A primer on functional programming for real world programs. In Japanese. Yen 2,940. <br />
<blockquote><br />
</blockquote><br />
<br />
<dt>[[Image:Purely_Functional_Data_Structures.jpg|Cover]] [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521663504 Purely Functional Data Structures]<br />
:[http://www.eecs.usma.edu/webs/people/okasaki/ Chris Okasaki], 232 pp., Cambridge University Press, 1998. ISBN 0-521-63124-6<BR> From the cover: <BLOCKQUOTE> Most books on data structures assume an imperative language like C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures and data structure design techniques from the point of view of functional languages. It includes code for a wide assortment both of classical data structures and of data structures developed exclusively for functional languages.This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study. [http://www.eecs.usma.edu/webs/people/okasaki/pfds-haskell.tar.gz Haskell source code for the book] </BLOCKQUOTE><br />
</DL><br />
<br />
<DT>[[Функциональное программирование на языке Haskell]]<br />
<br />
<DT>[[Справочник по языку Haskell]]<br />
<br />
<DT>[[Практика работы на языке Haskell]]<br />
<br />
<DT>[[14 занимательных эссе о языке Haskell и функциональном программировании]]<br />
<br />
<dt> <br />
[[Image:Cartea-lui-Dan-Popa-coperta-1.png|Cover]]<br><br />
[http://www.haskell.org/sitewiki/images/0/0f/Cartea-lui-Dan-Popa-coperta-1.png Download picture]<br><br />
[http://www.edusoft.ro/detalii.php?id=81 Introducere in Haskell 98 prin exemple ]: Dan Popa, 230 pp., Edusoft Bacau, Romania, (Ian, 31, 2007),Romanian, ISBN 978-973-8934-48-1 <BR> De pe coperta: <BLOCKQUOTE> (ro) Cartea este simultan un manual introductiv de Haskell si o carte auxiliara pentru studentii de la cursul de limbaje formale. Veti avea satisfactia cunoasterii unui limbaj modern (...) in care algoritmul de sortare Quicksort se scrie pe 6 randuri, asa cum se poate vedea de altfel si in imaginea de pe coperta I. (...) Cartea cuprinde o serie de capitole folosite la Universitatea Bacau in calitate de auxiliare de laborator la disciplina Limbaje Formale si Automate.<br />
<br><br />
(en) This book is simultaneosly a manual of Haskell and an auxiliary book for the students of the FLA course (Formal Languges and Automata). You will be satisfied by this modern language,Haskell. Why ? Using Haskell the Quicksort algorithm can be writen on 6 lines (or less), as you can see on the cover. And that's not all ... This book is used at Bacau State University, Romania. </BLOCKQUOTE><br />
<br />
<br />
===Foundations===<br />
<br />
;[[Image:TaPL.jpg|Cover]]<br />
[http://www.amazon.com/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091/ref=pd_sim_b_4/104-0009163-6568732 Types and Programming Languages]<br />
:Benjamin C. Pierce. 645 pages, The MIT Press, (February 1, 2002), English. ISBN 0262162091<br>From the cover:<br />
<blockquote> A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems--and of programming languages from a type-theoretic perspective-has important applications in software engineering, language design, high-performance compilers, and security. This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material. The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.</blockquote><br />
<br />
;[[Image:Advanced_TaPL.jpg|Cover]] [http://www.amazon.com/Advanced-Topics-Types-Programming-Languages/dp/0262162288/ref=pd_sim_b_1/104-0009163-6568732 Advanced Topics in Types and Programming Languages]<br />
:Benjamin C. Pierce (Editor), Hardcover: 608 pages, The MIT Press (December 23, 2004), Language: English, ISBN 0262162288.<br>From the cover:<br />
<blockquote> The study of type systems for programming languages now touches many areas of computer science, from language design and implementation to software engineering, network security, databases, and analysis of concurrent and distributed systems. This book offers accessible introductions to key ideas in the field, with contributions by experts on each topic. The topics covered include precise type analyses, which extend simple type systems to give them a better grip on the run time behavior of systems; type systems for low-level languages; applications of types to reasoning about computer programs; type theory as a framework for the design of sophisticated module systems; and advanced techniques in ML-style type inference. Advanced Topics in Types and Programming Languages builds on Benjamin Pierce's Types and Programming Languages (MIT Press, 2002); most of the chapters should be accessible to readers familiar with basic notations and techniques of operational semantics and type systems -- the material covered in the first half of the earlier book. Advanced Topics in Types and Programming Languages can be used in the classroom and as a resource for professionals. Most chapters include exercises, ranging in difficulty from quick comprehension checks to challenging extensions, many with solutions.<br />
</blockquote><br />
<br />
;[http://www-2.cs.cmu.edu/~rwh/plbook/ Programming Languages: Theory and Practice]<br />
:Robert Harper. (Draft). <blockquote> A working draft of a planned book on the theoretical foundations of practical programming languages. </blockquote><br />
<br />
;[http://homepages.cwi.nl/~jve/cs/ Computational Semantics and Type Theory]<br />
:Jan van Eijck. Draft. [http://www.cwi.nl/~jve/cs/cs.pdf Text online].<br />
<br />
;[http://www.cs.man.ac.uk/~pt/stable/Proofs+Types.html Proofs and Types]<br />
:By Jean-Yves Girard, translated and with appendices by Paul Taylor and Yves Lafont. Based on a short graduate course on typed lambda-calculus given at the Universit Paris VII in the autumn term of 1986-7.<br />
<br />
;[http://www.cs.uu.nl/wiki/Techno/ProgrammingLanguageTheoryTextsOnline Programming language theory texts online]<br />
:Collection of online programming language theory texts maintained by Frank Atanassow<br />
<br />
;[http://www.cs.chalmers.se/Cs/Research/Logic/book/ Programming in Martin-Löf's Type Theory: An Introduction]<br />
:Bengt Nordström, Kent Petersson and Jan M. Smith. 1990.<br />
<br />
===Monadic Programming===<br />
<br />
[[Image:Coperta5.jpg|left|Haskell - PIM]]<br />
<br />
==== Foreword of the book (en) ====<br />
<br />
I am delighted to introduce this book on the use of monads in Haskell as a way of structuring interpreters. In the early days, Haskell's most distinctive feature was lazy evaluation. Laziness forced us to take a pure approach to input/output, which meant that Haskell's I/O was initially rather weak. This weakness ultimately proved a strength, however, because it led us to the discovery that monads were not just an abstract mathematical concept, but were immediately applicable as a powerful program structuring mechanism.<br />
<br />
Monadic programming is not just to do with input/output: it is much more powerful. That is why I am pleased to see this book, which describes in some detail how to write a language interpreter using a monadic approach.<br />
<br />
In retrospect, the discovery of monads as a practical programming pattern is one of Haskell's most substantial contributions to the world of programming -- and it is one that you will share if you work through this book.<br />
<br />
I am also very happy to see Haskell growing in popularity among our brothers and sisters in Eastern Europe, and in Romania in particular. Enjoy!<br />
<br />
Simon P.J.<br />
<br />
<br />
<br />
===Mathematics===<br />
<br />
See [[Books and tutorials/Mathematics]]<br />
<br />
===Miscellaneous===<br />
<br />
[[Real World #haskell]]</div>Drbbhttps://wiki.haskell.org/index.php?title=Books&diff=43843Books2012-01-06T05:55:17Z<p>Drbb: /* . Foreword of the book (en) */</p>
<hr />
<div>Books covering many aspects of Haskell.<br />
<br />
==Language and library definition==<br />
<br />
<DL><br />
<DT>[[Image:Haskell_98_Language_and_Libraries.jpg|Cover]]<br />
Simon Peyton Jones: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521826144 "Haskell 98 language and libraries: the Revised Report"], Cambridge University Press, 2003, Hardback, 272 pages, ISBN 0521826144, £45.00<br />
<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
Haskell is the world's leading lazy functional programming language,<br />
widely used for teaching, research, and applications. The language<br />
continues to develop rapidly, but in 1998 the community decided to<br />
capture a stable snapshot of the language: Haskell 98. All Haskell<br />
compilers support Haskell 98, so practitioners and educators alike<br />
have a stable base for their work. This book constitutes the agreed<br />
definition of the Haskell 98, both the language itself and its<br />
supporting libraries. It has been considerably revised and refined<br />
since the original definition, and appears in print for the first<br />
time. It should be a standard reference work for anyone involved in<br />
research, teaching, or application of Haskell.<br />
</BLOCKQUOTE> <br />
The entire language definition is also available online:<br />
[[Language_and_library_specification|Language and library<br />
specification]].<br />
</DL><br />
<br />
==Textbooks==<br />
<br />
<DL><br />
<br />
<dt>[[Image:Lyah.png|Cover]] Miran Lipovača: [http://www.nostarch.com/lyah.htm <em>Learn You a Haskell for Great Good!</em>], Paperback: 360 pages, No Starch Press (April 2011), English, ISBN: 978-1-59327-283-8<br />
<blockquote><br />
<B>Book Description</B><BR><br />
It's all in the name: Learn You a Haskell for Great Good! is a hilarious, illustrated guide to this complex functional language. Packed with the author's original artwork, pop culture references, and most importantly, useful example code, this book teaches functional fundamentals in a way you never thought possible.<br />
</blockquote><br />
<br />
<dt>[[Image:Programming_in_Haskell.jpg|Cover]] Graham Hutton: [http://www.cs.nott.ac.uk/~gmh/book.html <em>Programming in Haskell</em>], Paperback: 200 pages, Cambridge University Press (January 31, 2007), English, ISBN 0521692695<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
Haskell is one of the leading languages for teaching functional<br />
programming, enabling students to write simpler and cleaner code, and to<br />
learn how to structure and reason about programs. This introduction is<br />
ideal for beginners: it requires no previous programming experience and<br />
all concepts are explained from first principles via carefully chosen<br />
examples. Each chapter includes exercises that range from the<br />
straightforward to extended projects, plus suggestions for further<br />
reading on more advanced topics. The author is a leading Haskell<br />
researcher and instructor, well-known for his teaching skills. The<br />
presentation is clear and simple, and benefits from having been refined<br />
and class-tested over several years. The result is a text that can be<br />
used with courses, or for self-learning. Features include: freely<br />
accessible Powerpoint slides for each chapter; solutions to exercises,<br />
and examination questions (with solutions) available to instructors;<br />
downloadable code that's fully compliant with the latest Haskell<br />
release.<br />
</blockquote><br />
<br />
<dt>[[Image:Rwh-thumb.png|Cover]] Bryan O'Sullivan, Don Stewart, and John Goerzen: [http://book.realworldhaskell.org/ <em>Real World Haskell</em>], Paperback: 700 pages, O'Reilly, November 2008, English, ISBN-10: 0596514980, ISBN-13: 978-0596514983<br />
<blockquote><br />
See ''[[Real World Haskell]]''. <br />
</blockquote><br />
<br />
<DT>[[Image:The_Haskell_School_of_Expression.jpg|Cover]] Paul Hudak: [http://plucky.cs.yale.edu/soe <EM>The Haskell School of Expression: Learning Functional Programming through Multimedia</EM>], Cambridge University Press, New York, 2000, 416<br />
pp, 15 line diagrams, 75 exercises, Paperback $29.95, ISBN 0521644089, Hardback $74.95, ISBN 0521643384<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
This book teaches functional programming as a way of thinking and<br />
problem solving, using Haskell, the most popular purely functional<br />
language. Rather than using the conventional mathematical examples<br />
commonly found in other programming language textbooks, the author<br />
draws examples from multimedia applications, including graphics,<br />
animation, and computer music, thus rewarding the reader with working<br />
programs for inherently more interesting applications. Aimed at both<br />
beginning and advanced programmers, this tutorial begins with a gentle<br />
introduction to functional programming and moves rapidly on to more<br />
advanced topics. An underlying theme is the design and implementation<br />
of <em>domain specific languages</em>, using three examples: FAL (a Functional<br />
Animation Language), IRL (an Imperative Robot Language), and MDL (a<br />
Music Description Language). Details about programming in Haskell<br />
are presented in boxes throughout the text so they can be easily<br />
referred to and found quickly.<br />
<br />
The book's [http://plucky.cs.yale.edu/soe Web Site] contains source files for all programs in the text, as well as the graphics libraries to run them under Windows and Linux platforms. It also contains PowerPoint slides useful for<br />
teaching a course using the textbook.<br />
<br />
*There is a review of SOE on this wiki: [[The Monad.Reader/Issue3/SoE Review]].<br />
</blockquote><br />
<DT>[[Image:The_Craft_of_Functional_Programming.jpg|Cover]] Simon Thompson: [http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/ <EM>Haskell: The Craft of Functional Programming</EM>], Second Edition,<br />
Addison-Wesley, 507&nbsp;pages, paperback, 1999. ISBN 0-201-34275-8.<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
The second edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice an program design, testing, problem solving and how to avoid common pitfalls. <br />
<br />
Building on the strengths of the first edition, the book includes many new and improved features: <br />
*Complete coverage of Haskell 98, the standard version of Haskell which will be stable and supported by implementations for years to come. <br />
*An emphasis on software engineering principles, encouraging a disciplined approach to building reusable libraries of software components. <br />
*Detailed coverage of the Hugs interpreter with an appendix covering other implementations. <br />
*A running case study of pictures emphasizes the built-in functions which appear in the standard prelude and libraries. It is also used to give an early preview of some of the more complex language features, such as high-order functions. <br />
*List comprehensions and the standard functions over lists are covered before recursion. <br />
*Early coverage of polymorphism supporting the "toolkit" approach and encouraging the resuse of built-in functions and types. <br />
*Extensive reference material containing details of further reading in books, journals and on the World Wide Web. <br />
*Accompanying Web Site supporting the book, containing all the program code, further teaching materials and other useful resources. <br />
<B>Synopsis</B><BR> <br />
This books introduces Haskell at a level appropriate for those with little or no prior experience of functional programming. The emphasis is on the process of crafting programs, solving problems, and avoiding common errors.<br />
</blockquote><br />
<br />
<DT>[[Image:Introduction_to_Functional_Programming.jpg|Cover]] Richard Bird: [http://www.prenhall.com/allbooks/ptr_0134843460.html <EM>Introduction to Functional Programming using Haskell</EM>], 2nd edition, Prentice Hall Press, 1998, 460 pp., ISBN 0-13-484346-0.<br />
<blockquote><br />
From the cover:<br />
<br />
After the success of the first edition, Introduction to Functional Programming using Haskell has been thoroughly updated and revised to provide a complete grounding in the principles and techniques of programming with functions.<br />
<br />
The second edition uses the popular language Haskell to express functional programs. There are new chapters on program optimisation, abstract datatypes in a functional setting, and programming in a monadic style. There are completely new case studies, and many new exercises.<br />
<br />
As in the first edition, there is an emphasis on the fundamental techniques for reasoning about functional programs, and for deriving them systematically from their specifications.<br />
<br />
The book is self-contained, assuming no prior knowledge of programming, and is suitable as an introductory undergraduate text for first- or second-year students.<br />
</blockquote><br />
<br />
<br />
<DT>[[Image:Introduction_to_Functional_Programming_Systems_Using_Haskell.jpg|Cover]] Antony Davie: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521277248 <EM>An Introduction to Functional Programming Systems Using Haskell</EM>], Cambridge University Press, 1992. ISBN 0-521-25830-8 (hardback). ISBN 0-521-27724-8 (paperback).<br />
<blockquote><br />
Cover:<br />
<br />
Functional programming is a style of programming that has become increasingly popular during the past few years.<br />
Applicative programs have the advantage of being almost immediately expressible as functional descriptions; they can<br />
be proved correct and transformed through the referential transparency property.<br />
<br />
This book presents the basic concepts of functional programming, using the language Haskell for examples. The author<br />
incorporates a discussion of lambda calculus and its relationship with Haskell, exploring the implications for<br />
raparallelism. Contents: SASL for Beginners / Examples of SASL Programming / More Advanced Applicative Programming<br />
Techniques / Lambda Calculus / The Relationship Between Lambda Calculus and SASL / Program Transformation and<br />
Efficiency / Correctness, Equivalence and Program Verification / Landin's SECD Machine and Related<br />
Implementations / Further Implementation Techniques / Special Purpose Hardware / The Applicative Style of<br />
Semantics / Other Applicative Languages / Implications for Parallelism / Functional Programming in Von Neumann<br />
Languages <br />
</blockquote><br />
<br />
<DT>[[Image:Algorithms_A_Functional_Approach.jpg|Cover]] Fethi Rabhi and Guy Lapalme: [http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html <EM> Algorithms: A functional programming approach</EM>], <br />
Addison-Wesley, 235&nbsp;pages, paperback, 1999. ISBN 0-201-59604-0<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
The authors challenge more traditional methods of teaching algorithms<br />
by using a functional programming context, with Haskell as an<br />
implementation language. This leads to smaller, clearer and more<br />
elegant programs which enable the programmer to understand the<br />
algorithm more quickly and to use that understanding to explore<br />
alternative solutions. <br><br />
<b>Key features:</b><br />
*Most chapters are self-contained and can be taught independently from each other.<br />
*All programs are in Haskell'98 and provided on a WWW site.<br />
*End of chapter exercises throughout.<br />
*Comprehensive index and bibliographical notes.<br />
<B>Synopsis</B><BR> <br />
The book is organised as a classic algorithms book according to topics<br />
such as Abstract Data Types, sorting and searching. It uses a<br />
succession of practical programming examples to develop in the reader<br />
problem-solving skills which can be easily transferred to other<br />
language paradigms. It also introduces the idea of capturing<br />
algorithmic design strategies (e.g. Divide-and-Conquer, Dynamic<br />
Programming) through higher-order functions.<br><br />
<b>Target audience</b><br><br />
The book is intended for computer science students taking algorithms<br />
and/or (basic or advanced) functional programming courses.<br />
</BLOCKQUOTE><br />
<br />
<dt>[[Image:Fun_of_Programming.jpg|Cover]] Jeremy Gibbons and Oege de Moor (eds.): [http://www.palgrave.com/catalogue/catalogue.asp?Title_Id=0333992857 <em>The Fun of Programming</em>],Palgrave, 2002, 288 pages. ISBN 0333992857.<br />
<blockquote><br />
<b>Book description:</b><br><br />
In this textbook, leading researchers give tutorial expositions on the current state of the art of functional<br />
programming. The text is suitable for an undergraduate course immediately following an introduction to<br />
functional programming, and also for self-study. All new concepts are illustrated by plentiful examples,<br />
as well as exercises. A [http://web.comlab.ox.ac.uk/oucl/publications/books/fop/ website] gives access to accompanying software.<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones: [http://research.microsoft.com/Users/simonpj/Papers/slpj-book-1987/index.htm <em>Implementation of Functional Programming] Language</em>], 500 pages, Prentice-Hall, 1987. ISBN 0134533259.<br />
<blockquote><br />
This 1987 book is now out of print, but it is now available [http://research.microsoft.com/Users/simonpj/Papers/slpj-book-1987/index.htm online] in its entirety.<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones, David Lester: [http://www.amazon.com/Implementing-Functional-Languages-Prentice-Hall-International/dp/0137219520/sr=1-1/qid=1162002704/ref=sr_1_1/104-0009163-6568732?ie=UTF8&s=books <em>Implementing Functional Languages</em>], Paperback: 288 pages, Prentice Hall (August 1992), English, ISBN 0137219520 <br><br />
<blockquote><br />
The book is out of print. The full sources and a postscript version are <br />
[http://research.microsoft.com/Users/simonpj/Papers/papers.html available for free].<br />
<br />
This book gives a practical approach to understanding the<br />
implementations of non-strict functional languages using lazy graph<br />
reduction. The emphasis of the book is on building working prototypes of<br />
several functional language implementations (template- instantiation,<br />
G-Machine, TIM, parallel G-Machine. In each case the authors provide a<br />
complete working prototype of a particular implementation, and then lead<br />
the reader through a sequence of improvements which expand its scope.<br />
This enables readers to develop, modify and experiment with their own<br />
implementations and for use as a source of practical laboratory work<br />
material.<br />
</blockquote><br />
<br />
<dt>[[Image:TTFP.jpg|Cover]] Simon Thompson: [http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201416670/sr=1-1/qid=1162002856/ref=sr_1_1/104-0009163-6568732?ie=UTF8&s=books <em>Type Theory and Functional Programming</em>], Addison-Wesley, 1991. ISBN 0-201-41667-0. Hardcover: 388 pages.<br />
<blockquote><br />
Now out of print, the original version is available [http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ here].<br />
<br />
<em>Preface</em>:<br />
Constructive Type theory has been a topic of research interest to computer scientists,<br />
mathematicians, logicians and philosophers for a number of years. For computer scientists it provides<br />
a framework which brings together logic and programming languages in a most elegant and fertile way:<br />
program development and verification can proceed within a single system. Viewed in a different way,<br />
type theory is a functional programming language with some novel features, such as the totality of<br />
all its functions, its expressive type system allowing functions whose result type depends upon the<br />
value of its input, and sophisticated modules and abstract types whose interfaces can contain logical<br />
assertions as well as signature information. A third point of view emphasizes that programs (or<br />
functions) can be extracted from proofs in the logic.<br />
</blockquote><br />
<br />
<DT>[[Image:Uma_Abordagem_Pratica.jpg|Cover]] Claudio Cesar de Sá and Marcio Ferreira da Silva: <em> Haskell: Uma Abordagem Prática</em>, [http://www.novatec.com.br Novatec Editora Ltda.], 2006, 296 pages, ISBN 85-7522-095-0. The price is R$ 62,00 (in Reais). Language: Portuguese<br />
<blockquote><br />
This book is being published by Novatec Editora Ltda. You can access directly [http://www.novateceditora.com.br/livros/haskell/ here].<br />
<br><br />
<b>Book description:</b><br><br />
This book brings a comprehensive vision of Haskell language. No <br />
knowledge in another functional programming language is expected. In <br />
addition, no background in programming is required. The book presents <br />
issues from basic up to an intermediate level; it also includes some <br />
advanced aspects of Haskell. The title of the book, <em>Haskell: Uma <br />
Abordagem Prática</em>, in English <em>Haskell: A Practical Approach</em>, is the essence of the book.<br />
The result is a text that can be used in courses of programming and paradigms languages.<br />
Finally, many practical examples can be found <br />
throughout the book.<br />
<br />
An additional page containing comments on this book is found here:<br />
[http://www2.joinville.udesc.br/~coca/index.php/Main/PaginaDoLivroDeHaskell].<br />
Other data as bibtex entry, cover's book in several formats, <br />
Winhugs-2001 for download, and so on. This page is Portuguese.<br />
</blockquote><br />
<br />
<dt>[[Image:portada.jpg|Cover]] Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo. [http://www.lcc.uma.es/~pepeg/pfHaskell/index.html <em>Razonando con Haskell</em>], Thompson 2004. ISBN 84-9732-277-0. Language: Spanish<br />
<blockquote><br />
Descripción El objetivo principal de este libro es el de servir como<br />
libro de texto de las asignaturas de Programación Declarativa<br />
correspondientes a los estudios de Informática o Ciencias de la<br />
Computación, y otras ciencias en general ( Matemáticas, Física, etc.).<br />
El texto es fruto de una larga experiencia docente de los autores dentro<br />
de las distintas asignaturas que desarrollan la Programación Funcional<br />
en distintas titulaciones de la Universidad de Málaga. Aún así, su<br />
lectura no queda condicionada a un conocimiento previo sobre lenguajes<br />
de programación (de computadores), ni sobre Informática. De esta forma,<br />
el libro puede ser utilizado por todo aquel que desee tener un<br />
conocimiento amplio sobre la Programación Funcional. <br />
</blockquote><br />
<br />
<dt>[[Image:haskell-jp.jpg|Cover]] [http://www.amazon.co.jp/gp/product/4839919623 Haskell Primer: The first functional language to learn]. Jun Mukai. In Japanese. Yen 2,730.<br />
<blockquote><br />
</blockquote><br />
<br />
<dt>[[Image:Haskell-jp-2.jpg|Cover]] [http://www.amazon.co.jp/gp/product/4797336021 Practical Haskell Programming], Minero Aoki and Nobuo Yamashita. A primer on functional programming for real world programs. In Japanese. Yen 2,940. <br />
<blockquote><br />
</blockquote><br />
<br />
<dt>[[Image:Purely_Functional_Data_Structures.jpg|Cover]] [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521663504 Purely Functional Data Structures]<br />
:[http://www.eecs.usma.edu/webs/people/okasaki/ Chris Okasaki], 232 pp., Cambridge University Press, 1998. ISBN 0-521-63124-6<BR> From the cover: <BLOCKQUOTE> Most books on data structures assume an imperative language like C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures and data structure design techniques from the point of view of functional languages. It includes code for a wide assortment both of classical data structures and of data structures developed exclusively for functional languages.This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study. [http://www.eecs.usma.edu/webs/people/okasaki/pfds-haskell.tar.gz Haskell source code for the book] </BLOCKQUOTE><br />
</DL><br />
<br />
<DT>[[Функциональное программирование на языке Haskell]]<br />
<br />
<DT>[[Справочник по языку Haskell]]<br />
<br />
<DT>[[Практика работы на языке Haskell]]<br />
<br />
<DT>[[14 занимательных эссе о языке Haskell и функциональном программировании]]<br />
<br />
<dt> <br />
[[Image:Cartea-lui-Dan-Popa-coperta-1.png|Cover]]<br><br />
[http://www.haskell.org/sitewiki/images/0/0f/Cartea-lui-Dan-Popa-coperta-1.png Download picture]<br><br />
[http://www.edusoft.ro/detalii.php?id=81 Introducere in Haskell 98 prin exemple ]: Dan Popa, 230 pp., Edusoft Bacau, Romania, (Ian, 31, 2007),Romanian, ISBN 978-973-8934-48-1 <BR> De pe coperta: <BLOCKQUOTE> (ro) Cartea este simultan un manual introductiv de Haskell si o carte auxiliara pentru studentii de la cursul de limbaje formale. Veti avea satisfactia cunoasterii unui limbaj modern (...) in care algoritmul de sortare Quicksort se scrie pe 6 randuri, asa cum se poate vedea de altfel si in imaginea de pe coperta I. (...) Cartea cuprinde o serie de capitole folosite la Universitatea Bacau in calitate de auxiliare de laborator la disciplina Limbaje Formale si Automate.<br />
<br><br />
(en) This book is simultaneosly a manual of Haskell and an auxiliary book for the students of the FLA course (Formal Languges and Automata). You will be satisfied by this modern language,Haskell. Why ? Using Haskell the Quicksort algorithm can be writen on 6 lines (or less), as you can see on the cover. And that's not all ... This book is used at Bacau State University, Romania. </BLOCKQUOTE><br />
<br />
<br />
===Foundations===<br />
<br />
;[[Image:TaPL.jpg|Cover]]<br />
[http://www.amazon.com/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091/ref=pd_sim_b_4/104-0009163-6568732 Types and Programming Languages]<br />
:Benjamin C. Pierce. 645 pages, The MIT Press, (February 1, 2002), English. ISBN 0262162091<br>From the cover:<br />
<blockquote> A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems--and of programming languages from a type-theoretic perspective-has important applications in software engineering, language design, high-performance compilers, and security. This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material. The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.</blockquote><br />
<br />
;[[Image:Advanced_TaPL.jpg|Cover]] [http://www.amazon.com/Advanced-Topics-Types-Programming-Languages/dp/0262162288/ref=pd_sim_b_1/104-0009163-6568732 Advanced Topics in Types and Programming Languages]<br />
:Benjamin C. Pierce (Editor), Hardcover: 608 pages, The MIT Press (December 23, 2004), Language: English, ISBN 0262162288.<br>From the cover:<br />
<blockquote> The study of type systems for programming languages now touches many areas of computer science, from language design and implementation to software engineering, network security, databases, and analysis of concurrent and distributed systems. This book offers accessible introductions to key ideas in the field, with contributions by experts on each topic. The topics covered include precise type analyses, which extend simple type systems to give them a better grip on the run time behavior of systems; type systems for low-level languages; applications of types to reasoning about computer programs; type theory as a framework for the design of sophisticated module systems; and advanced techniques in ML-style type inference. Advanced Topics in Types and Programming Languages builds on Benjamin Pierce's Types and Programming Languages (MIT Press, 2002); most of the chapters should be accessible to readers familiar with basic notations and techniques of operational semantics and type systems -- the material covered in the first half of the earlier book. Advanced Topics in Types and Programming Languages can be used in the classroom and as a resource for professionals. Most chapters include exercises, ranging in difficulty from quick comprehension checks to challenging extensions, many with solutions.<br />
</blockquote><br />
<br />
;[http://www-2.cs.cmu.edu/~rwh/plbook/ Programming Languages: Theory and Practice]<br />
:Robert Harper. (Draft). <blockquote> A working draft of a planned book on the theoretical foundations of practical programming languages. </blockquote><br />
<br />
;[http://homepages.cwi.nl/~jve/cs/ Computational Semantics and Type Theory]<br />
:Jan van Eijck. Draft. [http://www.cwi.nl/~jve/cs/cs.pdf Text online].<br />
<br />
;[http://www.cs.man.ac.uk/~pt/stable/Proofs+Types.html Proofs and Types]<br />
:By Jean-Yves Girard, translated and with appendices by Paul Taylor and Yves Lafont. Based on a short graduate course on typed lambda-calculus given at the Universit Paris VII in the autumn term of 1986-7.<br />
<br />
;[http://www.cs.uu.nl/wiki/Techno/ProgrammingLanguageTheoryTextsOnline Programming language theory texts online]<br />
:Collection of online programming language theory texts maintained by Frank Atanassow<br />
<br />
;[http://www.cs.chalmers.se/Cs/Research/Logic/book/ Programming in Martin-Löf's Type Theory: An Introduction]<br />
:Bengt Nordström, Kent Petersson and Jan M. Smith. 1990.<br />
<br />
===Monadic Programming===<br />
<br />
[[Image:Coperta5.jpg|left|Haskell - PIM]]<br />
<br />
====. Foreword of the book (en) === =<br />
<br />
I am delighted to introduce this book on the use of monads in Haskell as a way of structuring interpreters. In the early days, Haskell's most distinctive feature was lazy evaluation. Laziness forced us to take a pure approach to input/output, which meant that Haskell's I/O was initially rather weak. This weakness ultimately proved a strength, however, because it led us to the discovery that monads were not just an abstract mathematical concept, but were immediately applicable as a powerful program structuring mechanism.<br />
<br />
Monadic programming is not just to do with input/output: it is much more powerful. That is why I am pleased to see this book, which describes in some detail how to write a language interpreter using a monadic approach.<br />
<br />
In retrospect, the discovery of monads as a practical programming pattern is one of Haskell's most substantial contributions to the world of programming -- and it is one that you will share if you work through this book.<br />
<br />
I am also very happy to see Haskell growing in popularity among our brothers and sisters in Eastern Europe, and in Romania in particular. Enjoy!<br />
<br />
Simon P.J.<br />
<br />
<br />
<br />
===Mathematics===<br />
<br />
See [[Books and tutorials/Mathematics]]<br />
<br />
===Miscellaneous===<br />
<br />
[[Real World #haskell]]</div>Drbbhttps://wiki.haskell.org/index.php?title=Why_Haskell_matters&diff=43807Why Haskell matters2012-01-04T06:00:57Z<p>Drbb: /* Elegance */ Added type-signature and explanation.</p>
<hr />
<div>==What are functional programming languages?==<br />
Programming languages such as C/C++/Java/Python are called imperative programming languages because they consist of sequences of actions. The programmer quite explicitly tells the computer how to perform a task, step-by-step.<br />
Functional programming languages work differently. Rather than performing actions in a sequence, they evaluate expressions.<br />
<br />
=== The level of abstraction ===<br />
There are two areas that are fundamental to programming a computer - resource management and sequencing. Resource management (allocating registers and memory) has been the target of vast abstraction, most new languages (imperative as well as functional) have implemented garbage collection to remove resource management from the problem, and lets the programmer focus on the algorithm instead of the book-keeping task of allocating memory.<br />
Sequencing has also undergone some abstraction, although not nearly to the same extent. Imperative languages have done so by introducing new keywords and standard libraries. For example, most imperative languages have special syntax for constructing several slightly different loops, you no longer have to do all the tasks of managing these loops yourself.<br />
But imperative languages are based upon the notion of sequencing - they can never escape it completely. The only way to raise the level of abstraction in the sequencing area for an imperative language is to introduce more keywords or standard functions, thus cluttering up the language.<br />
This close relationship between imperative languages and the task of sequencing commands for the processor to execute means that imperative languages can never rise above the task of sequencing, and as such can never reach the same level of abstraction that functional programming languages can.<br />
<br />
In Haskell, the sequencing task is removed. You only care what the program is to compute not how or when it is computed. This makes Haskell a more flexible and easy to use language. Haskell tends to be part of the solution for a problem, not a part of the problem itself.<br />
<br />
=== Functions and side-effects in functional languages ===<br />
Functions play an important role in functional programming languages. Functions are considered to be values just like integers or strings. A function can return another function, it can take a function as a parameter, and it can even be constructed by composing functions.<br />
This offers a stronger "glue" to combine the modules of your program. A function that evaluates some expression can take part of the computation as an argument for instance, thus making the function more modular.<br />
You could also have a function construct another function. For instance, you could define a function "differentiate" that will differentiate a given function numerically. So if you then have a function "f" you could define "f' = differentiate f", and use it like you would normally in a mathematical context.<br />
These types of functions are called ''higher order functions''.<br />
<br />
Here is a short Haskell example of a function numOf that counts the number of elements in a list that satisfy a certain property.<br />
<br />
<haskell>numOf p xs = length (filter p xs)</haskell><br />
<br />
We will discuss Haskell syntax later, but what this line says is just "To get the result, filter the list xs by the test p and compute the length of the result".<br />
Now p is a function that takes an element and returns True or False determining whether the element passes or fails the test. So numOf is a higher order function, some of the functionality is passed to it as an argument. Notice that filter is also a higher order function, it takes the "test function" as an argument.<br />
Let's play with this function and define some more specialized functions from it.<br />
<br />
<haskell>numOfEven xs = numOf even xs</haskell><br />
<br />
Here we define the function numOfEven which counts the number of even elements in a list. Note that we do not need to explicitly declare xs as a parameter. We could just as well write numOfEven = numOf even. A very clear definition indeed. But we'll explicitly type out the parameters for now.<br />
<br />
Let's define a function which counts the number of elements that are greater or equal to 5 :<br />
<br />
<haskell>numOfGE5 xs = numOf (>=5) xs</haskell><br />
<br />
Here the test function is just ">=5" which is passed to numOf to give us the functionality we need.<br />
<br />
Hopefully you should now see that the modularity of functional programming allows us to define a generic functions where some of the functionality is passed as an argument, which we can later use to define shorthands for any specialized functions.<br />
This small example is somewhat trivial, it wouldn't be too hard to re-write the function definition for all the functions above, but for more complex functions this comes in handy.<br />
You can, for instance, write only one function for traversing an auto-balancing binary tree and have it take some of the functionality as a parameter (for instance the comparison function). This would allow you to traverse the tree for any data type by simply providing the relevant comparison function for your needs. Thus you can expend some effort in making sure the general function is correct, and then all the specialized functions will also be correct. Not to mention you wouldn't have to copy and paste code all over your project.<br />
This concept is possible in some imperative languages as well. In some object oriented languages you often have to provide a "Comparator object" for trees and other standard data structures. The difference is that the Haskell way is a lot more intuitive and elegant (creating a separate type just for comparing two other types and then passing an object of this type is hardly an elegant way of doing it), so it's more likely to be used frequently (and not just in the standard libraries).<br />
<br />
A central concept in functional languages is that the result of a function is determined by its input, and only by its input. There are no side-effects! This extends to variables as well - ''variables in Haskell do not vary''. This may sound strange if you're used to imperative programming (where ''most'' of the code consists of changing the "contents" of a variable), but it's really quite natural. A variable in Haskell is a name that is bound to some value, rather than an abstraction of some low-level concept of a memory cell like in imperative languages. When variables are thought of as short-hands for values (just like they are in mathematics), it makes perfect sense that variable updates are not allowed. You wouldn't expect "4 = 5" to be a valid assignment in ''any'' language, so it's really quite strange that "x = 4; x = 5" is.<br />
This is often hard to grasp for programmers who are very used to imperative languages, but it isn't as strange as it first seems. So when you start thinking things like "This is too weird, I'm going back to C++!", try to force yourself to continue learning Haskell - you'll be glad you did.<br />
<br />
Removing side-effects from the equation allows expressions to be evaluated in any order. A function will always return the same result if passed the same input - no exceptions.<br />
This determinism removes a whole class of bugs found in imperative programs. In fact, you could even argue that ''most'' bugs in large systems can be traced back to side-effects - if not directly caused by them, then caused by a flawed design that relies on side-effects.<br />
This means that functional programs tend to have far fewer bugs than imperative ones.<br />
<br />
=== Conclusion ===<br />
Because functional languages are more intuitive and offer more and easier ways to get the job done, functional programs tend to be shorter (usually between 2 to 10 times shorter). The semantics are most often a lot closer to the problem than an imperative version, which makes it easier to verify that a function is correct. Furthermore Haskell doesn't allow side-effects, which leads to fewer bugs. Thus Haskell programs are easier to write, more robust, and easier to maintain.<br />
<br />
== What can Haskell offer the programmer? ==<br />
Haskell is a modern general purpose language developed to incorporate the collective wisdom of the functional programming community into one elegant, powerful and general language.<br />
<br />
===Purity===<br />
Unlike some other functional programming languages Haskell is pure. It doesn't allow ''any'' side-effects. This is probably the most important feature of Haskell. We've already briefly discussed the benefits of pure, side-effect free, programming - and there's not much more we can say about that. You'll need to experience it yourself.<br />
<br />
===Laziness===<br />
Another feature of Haskell is that it is lazy (technically speaking, it's "non-strict"). This means that nothing is evaluated until it has to be evaluated. You could, for instance, define an infinite list of primes without ending up in infinite recursion. Only the elements of this list that are actually used will be computed. This allows for some very elegant solutions to many problems. A typical pattern of solving a problem would be to define a list of all possible solutions and then filtering away the illegal ones. The remaining list will then only contain legal solutions. Lazy evaluation makes this operation very clean. If you only need one solution you can simply extract the first element of the resulting list - lazy evaluation will make sure that nothing is needlessly computed.<br />
<br />
===Strong typing===<br />
Furthermore Haskell is strongly typed, this means just what it sounds like. It's impossible to inadvertently convert a Double to an Int, or follow a null pointer. This also leads to fewer bugs. It might be a pain in the neck in the rare cases where you need to convert an Int to a Double explicitly before performing some operation, but in practice this doesn't happen often enough to become a nuisance. In fact, forcing each conversion to be explicit often helps to highlight problem code.<br />
In other languages where these conversions are invisible, problems often arise when the compiler treats a double like an integer or, even worse, an integer like a pointer.<br />
<br />
Unlike other strongly typed languages types in Haskell are automatically inferred. This means that you very rarely have to declare the types of your functions, except as a means of code documentation. Haskell will look at how you use the variables and figure out from there what type the variable should be - then it will all be type-checked to ensure there are no type-mismatches. <br />
Python has the notion of "duck typing", meaning "If it walks and talks like a duck, it's a duck!". You could argue that Haskell has a much better form of duck typing. If a value walks and talks like a duck, then it will be considered a duck through type inference, but unlike Python the compiler will also catch errors if later on it tries to bray like a donkey!<br />
So you get the benefits of strong typing (bugs are caught at compile-time, rather than run-time) without the hassle that comes with it in other languages.<br />
Furthermore Haskell will always infer the most general type on a variable. So if you write, say, a sorting function without a type declaration, Haskell will make sure the function will work for all values that can be sorted.<br />
<br />
Compare how you would do this in certain object oriented languages. To gain polymorphism you would have to use some base class, and then declare your variables as instances of subclasses to this base class. It all amounts to tons of extra work and ridiculously complex declarations just to proclaim the existence of a variable. Furthermore you would have to perform tons of type conversions via explicit casts - definitely not a particularly elegant solution.<br />
If you want to write a polymorphic function in these object oriented languages you would probably declare the parameters as an object of a global base class (like "Object" in Java), which essentially allows the programmer to send anything into the function, even objects which can't logically be passed to the function. The end result is that most functions you write in these languages are not general, they only work on a single data type. You're also moving the error checking from compile-time to run-time. In large systems where some of the functionality is rarely used, these bugs might never be caught until they cause a fatal crash at the worst possible time.<br />
<br />
Haskell provides an elegant, concise and safe way to write your programs. Programs will not crash unexpectedly, nor produce strangely garbled output.<br />
<br />
===Elegance===<br />
Another property of Haskell that is very important to the programmer, even though it doesn't mean as much in terms of stability or performance, is the elegance of Haskell. To put it simply: stuff just works like you'd expect it to.<br />
<br />
To highlight the elegance of Haskell we shall now take a look at a small example. We choose QuickSort-inspired filtering sort because it's a simple algorithm that is actually useful. We will look at two versions - one written in C++, an imperative language, and one written in Haskell.<br />
Both versions use only the functionality available to the programmer without importing any extra modules (otherwise we could just call "sort" in each language's standard library and be done with it!). Thus, we use the standard sequence primitives of each language (a "list" in Haskell and an "array" in C++). Both versions must also be polymorphic (which is done "automatically" in Haskell, and with templates in C++). Both versions must use the same recursive algorithm.<br />
<br />
Please note that this is ''not'' intended as a definite comparison between the two languages. It's intended to show the elegance of Haskell, the C++ version is only included for comparison (and would be coded quite differently if you used the standard QuickSort algorithm or the Standard Template Libraries (STL), for example).<br />
<br />
template <typename T><br />
void qsort (T *result, T *list, int n)<br />
{<br />
if (n == 0) return;<br />
T *smallerList, *largerList;<br />
smallerList = new T[n];<br />
largerList = new T[n]; <br />
T pivot = list[0];<br />
int numSmaller=0, numLarger=0; <br />
for (int i = 1; i < n; i++)<br />
if (list[i] < pivot)<br />
smallerList[numSmaller++] = list[i];<br />
else <br />
largerList[numLarger++] = list[i];<br />
<br />
qsort(smallerList,smallerList,numSmaller); <br />
qsort(largerList,largerList,numLarger);<br />
<br />
int pos = 0; <br />
for ( int i = 0; i < numSmaller; i++)<br />
result[pos++] = smallerList[i];<br />
<br />
result[pos++] = pivot;<br />
<br />
for ( int i = 0; i < numLarger; i++)<br />
result[pos++] = largerList[i];<br />
<br />
delete [] smallerList;<br />
delete [] largerList;<br />
};<br />
<br />
We will not explain this code further, just note how complex and difficult it is to understand at a glance, largely due to the programmer having to deal with low-level details which have nothing to do with the task at hand.<br />
Now, let's take a look at a Haskell version of FilterSort, which might look a something like this.<br />
<br />
<haskell><br />
<br />
qsort :: (Ord a) => [a] -> [a]<br />
qsort [] = []<br />
qsort (x:xs) = qsort less ++ [x] ++ qsort more<br />
where less = filter (<x) xs<br />
more = filter (>=x) xs<br />
</haskell><br />
<br />
(This implementation has very poor runtime and space complexity, but that can be [http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html improved, at the expense of some of the elegance].)<br />
<br />
Let's dissect this code in detail, since it uses quite a lot of Haskell syntax that you might not be familiar with.<br />
<br />
The first line is a type signature. It declares "qsort" to be function that takes a list "[a]" as input and returns ("->") another list "[a]". "a" is a type variable (vaguely similar to a C++ template declaration), and "(Ord a)" is a constraint that means that only types that have an ordering are allowed. This function is a generic ("template") function, that can sort any list of pairwise-comparable objects. The phrase "(Ord a) => [a] -> [a]" means "if the type 'a' is ordered, than a list of 'a' can be passed in, and another list of 'a' will come out."<br />
<br />
The function is called qsort and takes a list as a parameter. We define a function in Haskell like so: funcname a b c = expr, where funcname is the name of the function, a, b, and, c are the parameters and expr is the expression to be evaluated (most often using the parameters). Functions are called by simply putting the function name first and then the parameter(s). Haskell doesn't use parenthesis for function application. Functions simply bind more tightly than anything else, so "f 5 * 2", for instance, would apply f to 5 and then multiply by 2, if we wanted the multiplication to occur before the function application then we would use parenthesis like so "f (5*2)".<br />
<br />
Let's get back to FilterSort.<br />
First we see that we have two definitions of the functions. This is called pattern matching and we can briefly say that it will test the argument passed to the function top-to-bottom and use the first one that matches.<br />
The first definition matches against [] which in Haskell is the empty list (a list of 1,2 and 3 is [1,2,3] so it makes sense that an empty list is just two brackets).<br />
So when we try to sort an empty list, the result will be an empty list. Sounds reasonable enough, doesn't it?<br />
The second definition pattern matches against a list with at least one element. It does this by using (x:xs) for its argument. The "cons" operator is (:) and it simply puts an element in front of a list, so that 0 : [1,2,3] returns [0,1,2,3]. Pattern matching against (x:xs) is a match against the list with the head x and the tail xs (which may or may not be the empty list). In other words, (x:xs) is a list of at least one element.<br />
So since we will need to use the head of the list later, we can actually extract this very elegantly by using pattern matching. You can think of it as naming the contents of the list. This can be done on any data construct, not just a list. It is possible to pattern match against an arbitrary variable name and then use the head function on that to retrieve the head of the list.<br />
Now if we have a non empty list, the sorted list is produced by sorting all elements that are smaller than x and putting that in front of x, then we sort all elements larger than x and put those at the end. We do this by using the list concatenation operator ++. Notice that x is not a list so the ++ operator won't work on it alone, which is why we make it a singleton-list by putting it inside brackets.<br />
So the function reads "To sort the list, sandwich the head between the sorted list of all elements smaller than the head, and the sorted list of all elements larger than the head". Which could very well be the original algorithm description. This is very common in Haskell. A function definition usually resembles the informal description of the function very closely. This is why I say that Haskell has a smaller semantic gap than other languages.<br />
<br />
But wait, we're not done yet! How is the list less and more computed? Well, remember that we don't care about sequencing in Haskell, so we've defined them below the function using the where notation (which allows any definitions to use the parameters of the function to which they belong). We use the standard prelude function filter, I won't elaborate too much on this now, but the line less = filter (<x) xs will use filter (<x) xs to filter the list xs. You can see that we actually pass the function which will be used to filter the list to filter, an example of higher order functions.<br />
The function (<x) should be read out "the function 'less than x'" and will return True if an element passed to it is less than x (notice how easy it was to construct a function on the fly, we put the expression "<x", "less than x", in parenthesis and sent it off to the function - functions really are just another value!).<br />
All elements that pass the test are output from the filter function and put inside less. In a same way (>=x) is used to filter the list for all elements larger than or equal to x.<br />
<br />
Now that you've had the syntax explained to you, read the function definition again. Notice how little time it takes to get an understanding about what the function does. The function definitions in Haskell explain what it computes, not how.<br />
<br />
If you've already forgotten the syntax outlined above, don't worry! We'll go through it more thoroughly and at a slower pace in the tutorials. The important thing to get from this code example is that Haskell code is elegant and intuitive.<br />
<br />
===Haskell and bugs===<br />
We have several times stated that various features of Haskell help fight the occurrence of bugs. Let's recap these.<br />
<br />
Haskell programs have fewer bugs because Haskell is:<br />
<br />
* '''Pure'''. There are no side effects.<br />
<br />
* '''Strongly typed'''. There can be no dubious use of types. And No Core Dumps!<br />
<br />
* '''Concise'''. Programs are shorter which make it easier to look at a function and "take it all in" at once, convincing yourself that it's correct.<br />
<br />
* '''High level'''. Haskell programs most often reads out almost exactly like the algorithm description. Which makes it easier to verify that the function does what the algorithm states. By coding at a higher level of abstraction, leaving the details to the compiler, there is less room for bugs to sneak in.<br />
<br />
* '''Memory managed'''. There's no worrying about dangling pointers, the Garbage Collector takes care of all that. The programmer can worry about implementing the algorithm, not book-keeping of the memory.<br />
<br />
* '''Modular'''. Haskell offers stronger and more "glue" to compose your program from already developed modules. Thus Haskell programs can be more modular. Often used modular functions can thus be proven correct by induction. Combining two functions that are proven to be correct, will also give the correct result (assuming the combination is correct).<br />
<br />
Furthermore most people agree that you just think differently when solving problems in a functional language. You subdivide the problem into smaller and smaller functions and then you write these small (and "almost-guaranteed-to-be-correct") functions, which are composed in various ways to the final result. There just isn't any room for bugs!<br />
<br />
<br />
== Haskell vs OOP ==<br />
The great benefit of Object Oriented Programming is rarely that you group your data with the functions that act upon it together into an object - it's that it allows for great data encapsulation (separating the interface from implementation) and polymorphism (letting a whole set of data types behave the same way). However:<br />
<br />
''Data encapsulation and polymorphism are not exclusive to OOP!''<br />
<br />
Haskell has tools for abstracting data. We can't really get into it without first going through the module system and how abstract data types (ADT) work in Haskell, something which is well beyond the scope of this essay. We will therefore settle for a short description of how ADTs and polymorphism works in Haskell.<br />
<br />
Data encapsulation is done in Haskell by declaring each data type in a separate module, from this module you only export the interface. Internally there might be a host of functions that touch the actual data, but the interface is all that's visible from outside of the module.<br />
Note that the data type and the functions that act upon the data type are not grouped into an "object", but they are (typically) grouped into the same module, so you can choose to only export certain functions (and not the constructors for the data type) thus making these functions the only way to manipulate the data type - "hiding" the implementation from the interface.<br />
<br />
Polymorphism is done by using something called type classes. Now, if you come from a C++ or Java background you might associate classes with something resembling a template for how to construct an object, but that's not what they mean in Haskell. A type class in Haskell is really just what it sounds like. It's a set of rules for determining whether a type is an instance of that class.<br />
So Haskell separates the class instantiation and the construction of the data type. You might declare a type "Porsche", to be an instance of the "Car" type class, say. All functions that can be applied onto any other member of the Car type class can then be applied to a Porsche as well.<br />
A class that's included with Haskell is the Show type class, for which a type can be instantiated by providing a show function, which converts the data type to a String. Consequently almost all types in Haskell can be printed onto the screen by applying show on them to convert them to a String, and then using the relevant IO action (more on IO in the tutorials).<br />
Note how similar this is to the the object notion in OOP when it comes to the polymorphism aspect.<br />
The Haskell system is a more intuitive system for handling polymorphism. You won't have to worry about inheriting in the correct hierarchical order or to make sure that the inheritance is even sensible. A class is just a class, and types that are instances of this class really doesn't have to share some parent-child inheritance relationship. If your data type fulfills the requirements of a class, then it can be instantiated in that class. Simple, isn't it?<br />
Remember the QuickSort example? Remember that I said it was polymorphic? The secret behind the polymorphism in qsort is that it is defined to work on any type in the Ord type class (for "Ordered"). Ord has a set of functions defined, among them is "<" and ">=" which are sufficient for our needs because we only need to know whether an element is smaller than x or not. So if we were to define the Ord functions for our Porsche type (it's sufficient to implement, say, <= and ==, Haskell will figure out the rest from those) in an instantiation of the Ord type class, we could then use qsort to sort lists of Porsches (even though sorting Porsches might not make sense).<br />
Note that we never say anything about which classes the elements of the list must be defined for, Haskell will infer this automatically from just looking at which functions we have used (in the qsort example, only "<" and ">=" are relevant).<br />
<br />
So to summarize: Haskell does include mechanisms for data encapsulation that match or surpass those of OOP languages. The only thing Haskell does not provide is a way to group functions and data together into a single "object" (aside from creating a data type which includes a function - remember, functions are data!). This is, however, a very minor problem. To apply a function to an object you would write "func obj a b c" instead of something like "obj.func a b c".<br />
<br />
<br />
== Modularity ==<br />
A central concept in computing is modularity. A popular analogy is this: say you wanted to construct a wooden chair. If you construct the parts of it separately, and then glue them together, the task is solved easily. But if you were to carve the whole thing out of a solid piece of wood, it would prove to be quite a bit harder. John Hughes had this to say on the topic in his paper [http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters]<br />
<br />
''"Languages which aim to improve productivity must support modular programming well. But new scope rules and mechanisms for separate compilation are not enough - modularity means more than modules. Our ability to decompose a problem into parts depends directly on our ability to glue solutions together. To assist modular programming, a language must provide good glue.''<br />
<br />
''Functional programming languages provide two new kinds of glue - higher-order functions and lazy evaluation."''<br />
<br />
<br />
==The speed of Haskell ==<br />
Let me first state clearly that the following only applies to the general case in which speed isn't absolutely critical, where you can accept a few percent longer execution time for the benefit of reducing development time greatly. There are cases when speed is the primary concern, and then the following section will not apply to the same extent.<br />
<br />
Now, some C++ programmers might claim that the C++ version of QuickSort above is probably a bit faster than the Haskell version. And this might be true. For most applications, though, the difference in speed is so small that it's utterly irrelevant. For instance, take a look at the [http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=all Computer Language Benchmarks Game], where Haskell compares favorably to most of the so called "fast" languages.<br />
Now, these benchmarks don't prove all that much about real-world performance, but they do show that Haskell isn't as slow as some people think. At the time of writing it's in 4th position, only slightly behind C and C++.<br />
<br />
Almost all programs in use today have a fairly even spread of processing time among its functions. The most notable exceptions are applications like MPEG encoders, and artificial benchmarks, which spend a large portion of their execution time within a small portion of the code. If you ''really'' need speed at all costs, consider using C instead of Haskell.<br />
<br />
There's an old rule in computer programming called the "80/20 rule". It states that 80% of the time is spent in 20% of the code. The consequence of this is that any given function in your system will likely be of minimal importance when it comes to optimizations for speed. There may be only a handful of functions important enough to optimize. These important functions could be written in C (using the excellent foreign function interface in Haskell). The role of C could, and probably will, take over the role of assembler programming - you use it for the really time-critical bits of your system, but not for the whole system itself.<br />
<br />
We should continue to move to higher levels of abstraction, just like we've done before. We should trade application speed for increased productivity, stability and maintainability. Programmer time is almost always more expensive than CPU time.<br />
We aren't writing applications in assembler anymore for the same reason we shouldn't be writing applications in C anymore.<br />
<br />
Finally remember that algorithmic optimization can give much better results than code optimization. For theoretical examples when factors such as development times and stability doesn't matter, then sure, C is often faster than Haskell. But in the real world development times ''do'' matter, this isn't the case. If you can develop your Haskell application in one tenth the time it would take to develop it in C (from experience, this is not at all uncommon) you will have lots of time to profile and implement new algorithims. So in the "real world" where we don't have infinite amounts of time to program our applications, Haskell programs can often be much faster than C programs.<br />
<br />
== Epilogue ==<br />
So if Haskell is so great, how come it isn't "mainstream"? Well, one reason is that the operating system is probably written in C or some other imperative language, so if your application mainly interacts with the internals of the OS, you may have an easier time using imperative languages. Another reason for the lack of Haskell, and other functional languages, in mainstream use is that programming languages are rarely thought of as tools (even though they are). To most people their favorite programming language is much more like religion - it just seems unlikely that any other language exists that can get the job done better and faster.<br />
<br />
There is an essay by Paul Graham called [http://www.paulgraham.com/avg.html Beating the Averages] describing his experience using Common Lisp, another functional language, for an upstart company. In it he uses an analogy which he calls "The Blub Paradox".<br />
<br />
It goes a little something like this:<br />
If a programmer's favorite language is Blub, which is positioned somewhere in the middle of the "power spectrum", he can most often only identify languages that are lower down in the spectrum. He can look at COBOL and say "How can anyone get anything done in that language, it doesn't have feature x", x being a feature in Blub.<br />
<br />
However, this Blub programmer has a harder time looking the other way in the spectrum. If he examines languages that are higher up in the power spectrum, they will just seem "weird" because the Blub programmer is "thinking in Blub" and can not possibly see the uses for various features of more powerful languages. It goes without saying that this inductively leads to the conclusion that to be able to compare all languages you'll need to position yourself at the top of the power spectrum. It is my belief that functional languages, almost by definition, are closer to the top of the power spectrum than imperative ones.<br />
So languages can actually limit a programmers frame of thought. If all you've ever programmed is Blub, you may not see the limitations of Blub - you may only do that by switching to another level which is more powerful.<br />
<br />
One of the reasons the mainstream doesn't use Haskell is because people feel that "their" language does "everything they need". And of course it does, because they are thinking in Blub! Languages aren't just technology, it's a way of thinking. And if you're not thinking in Haskell, it is very hard to see the use of Haskell - even if Haskell would allow you to write better applications in a shorter amount of time!<br />
<br />
Hopefully this article has helped you break out of the Blub paradox. Even though you may not yet "think in Haskell", it is my hope that you are at least aware of any limitations in your frame of thought imposed by your current "favorite" language, and that you now have more motivation to expand it by learning something new.<br />
<br />
If you are committed to learn a functional language, to get a better view of the power spectrum, then Haskell is an excellent candidate.<br />
<br />
[[Category:Tutorials]]</div>Drbbhttps://wiki.haskell.org/index.php?title=Why_Haskell_matters&diff=43806Why Haskell matters2012-01-04T05:53:26Z<p>Drbb: /* Elegance */ QuickSort clarifications.</p>
<hr />
<div>==What are functional programming languages?==<br />
Programming languages such as C/C++/Java/Python are called imperative programming languages because they consist of sequences of actions. The programmer quite explicitly tells the computer how to perform a task, step-by-step.<br />
Functional programming languages work differently. Rather than performing actions in a sequence, they evaluate expressions.<br />
<br />
=== The level of abstraction ===<br />
There are two areas that are fundamental to programming a computer - resource management and sequencing. Resource management (allocating registers and memory) has been the target of vast abstraction, most new languages (imperative as well as functional) have implemented garbage collection to remove resource management from the problem, and lets the programmer focus on the algorithm instead of the book-keeping task of allocating memory.<br />
Sequencing has also undergone some abstraction, although not nearly to the same extent. Imperative languages have done so by introducing new keywords and standard libraries. For example, most imperative languages have special syntax for constructing several slightly different loops, you no longer have to do all the tasks of managing these loops yourself.<br />
But imperative languages are based upon the notion of sequencing - they can never escape it completely. The only way to raise the level of abstraction in the sequencing area for an imperative language is to introduce more keywords or standard functions, thus cluttering up the language.<br />
This close relationship between imperative languages and the task of sequencing commands for the processor to execute means that imperative languages can never rise above the task of sequencing, and as such can never reach the same level of abstraction that functional programming languages can.<br />
<br />
In Haskell, the sequencing task is removed. You only care what the program is to compute not how or when it is computed. This makes Haskell a more flexible and easy to use language. Haskell tends to be part of the solution for a problem, not a part of the problem itself.<br />
<br />
=== Functions and side-effects in functional languages ===<br />
Functions play an important role in functional programming languages. Functions are considered to be values just like integers or strings. A function can return another function, it can take a function as a parameter, and it can even be constructed by composing functions.<br />
This offers a stronger "glue" to combine the modules of your program. A function that evaluates some expression can take part of the computation as an argument for instance, thus making the function more modular.<br />
You could also have a function construct another function. For instance, you could define a function "differentiate" that will differentiate a given function numerically. So if you then have a function "f" you could define "f' = differentiate f", and use it like you would normally in a mathematical context.<br />
These types of functions are called ''higher order functions''.<br />
<br />
Here is a short Haskell example of a function numOf that counts the number of elements in a list that satisfy a certain property.<br />
<br />
<haskell>numOf p xs = length (filter p xs)</haskell><br />
<br />
We will discuss Haskell syntax later, but what this line says is just "To get the result, filter the list xs by the test p and compute the length of the result".<br />
Now p is a function that takes an element and returns True or False determining whether the element passes or fails the test. So numOf is a higher order function, some of the functionality is passed to it as an argument. Notice that filter is also a higher order function, it takes the "test function" as an argument.<br />
Let's play with this function and define some more specialized functions from it.<br />
<br />
<haskell>numOfEven xs = numOf even xs</haskell><br />
<br />
Here we define the function numOfEven which counts the number of even elements in a list. Note that we do not need to explicitly declare xs as a parameter. We could just as well write numOfEven = numOf even. A very clear definition indeed. But we'll explicitly type out the parameters for now.<br />
<br />
Let's define a function which counts the number of elements that are greater or equal to 5 :<br />
<br />
<haskell>numOfGE5 xs = numOf (>=5) xs</haskell><br />
<br />
Here the test function is just ">=5" which is passed to numOf to give us the functionality we need.<br />
<br />
Hopefully you should now see that the modularity of functional programming allows us to define a generic functions where some of the functionality is passed as an argument, which we can later use to define shorthands for any specialized functions.<br />
This small example is somewhat trivial, it wouldn't be too hard to re-write the function definition for all the functions above, but for more complex functions this comes in handy.<br />
You can, for instance, write only one function for traversing an auto-balancing binary tree and have it take some of the functionality as a parameter (for instance the comparison function). This would allow you to traverse the tree for any data type by simply providing the relevant comparison function for your needs. Thus you can expend some effort in making sure the general function is correct, and then all the specialized functions will also be correct. Not to mention you wouldn't have to copy and paste code all over your project.<br />
This concept is possible in some imperative languages as well. In some object oriented languages you often have to provide a "Comparator object" for trees and other standard data structures. The difference is that the Haskell way is a lot more intuitive and elegant (creating a separate type just for comparing two other types and then passing an object of this type is hardly an elegant way of doing it), so it's more likely to be used frequently (and not just in the standard libraries).<br />
<br />
A central concept in functional languages is that the result of a function is determined by its input, and only by its input. There are no side-effects! This extends to variables as well - ''variables in Haskell do not vary''. This may sound strange if you're used to imperative programming (where ''most'' of the code consists of changing the "contents" of a variable), but it's really quite natural. A variable in Haskell is a name that is bound to some value, rather than an abstraction of some low-level concept of a memory cell like in imperative languages. When variables are thought of as short-hands for values (just like they are in mathematics), it makes perfect sense that variable updates are not allowed. You wouldn't expect "4 = 5" to be a valid assignment in ''any'' language, so it's really quite strange that "x = 4; x = 5" is.<br />
This is often hard to grasp for programmers who are very used to imperative languages, but it isn't as strange as it first seems. So when you start thinking things like "This is too weird, I'm going back to C++!", try to force yourself to continue learning Haskell - you'll be glad you did.<br />
<br />
Removing side-effects from the equation allows expressions to be evaluated in any order. A function will always return the same result if passed the same input - no exceptions.<br />
This determinism removes a whole class of bugs found in imperative programs. In fact, you could even argue that ''most'' bugs in large systems can be traced back to side-effects - if not directly caused by them, then caused by a flawed design that relies on side-effects.<br />
This means that functional programs tend to have far fewer bugs than imperative ones.<br />
<br />
=== Conclusion ===<br />
Because functional languages are more intuitive and offer more and easier ways to get the job done, functional programs tend to be shorter (usually between 2 to 10 times shorter). The semantics are most often a lot closer to the problem than an imperative version, which makes it easier to verify that a function is correct. Furthermore Haskell doesn't allow side-effects, which leads to fewer bugs. Thus Haskell programs are easier to write, more robust, and easier to maintain.<br />
<br />
== What can Haskell offer the programmer? ==<br />
Haskell is a modern general purpose language developed to incorporate the collective wisdom of the functional programming community into one elegant, powerful and general language.<br />
<br />
===Purity===<br />
Unlike some other functional programming languages Haskell is pure. It doesn't allow ''any'' side-effects. This is probably the most important feature of Haskell. We've already briefly discussed the benefits of pure, side-effect free, programming - and there's not much more we can say about that. You'll need to experience it yourself.<br />
<br />
===Laziness===<br />
Another feature of Haskell is that it is lazy (technically speaking, it's "non-strict"). This means that nothing is evaluated until it has to be evaluated. You could, for instance, define an infinite list of primes without ending up in infinite recursion. Only the elements of this list that are actually used will be computed. This allows for some very elegant solutions to many problems. A typical pattern of solving a problem would be to define a list of all possible solutions and then filtering away the illegal ones. The remaining list will then only contain legal solutions. Lazy evaluation makes this operation very clean. If you only need one solution you can simply extract the first element of the resulting list - lazy evaluation will make sure that nothing is needlessly computed.<br />
<br />
===Strong typing===<br />
Furthermore Haskell is strongly typed, this means just what it sounds like. It's impossible to inadvertently convert a Double to an Int, or follow a null pointer. This also leads to fewer bugs. It might be a pain in the neck in the rare cases where you need to convert an Int to a Double explicitly before performing some operation, but in practice this doesn't happen often enough to become a nuisance. In fact, forcing each conversion to be explicit often helps to highlight problem code.<br />
In other languages where these conversions are invisible, problems often arise when the compiler treats a double like an integer or, even worse, an integer like a pointer.<br />
<br />
Unlike other strongly typed languages types in Haskell are automatically inferred. This means that you very rarely have to declare the types of your functions, except as a means of code documentation. Haskell will look at how you use the variables and figure out from there what type the variable should be - then it will all be type-checked to ensure there are no type-mismatches. <br />
Python has the notion of "duck typing", meaning "If it walks and talks like a duck, it's a duck!". You could argue that Haskell has a much better form of duck typing. If a value walks and talks like a duck, then it will be considered a duck through type inference, but unlike Python the compiler will also catch errors if later on it tries to bray like a donkey!<br />
So you get the benefits of strong typing (bugs are caught at compile-time, rather than run-time) without the hassle that comes with it in other languages.<br />
Furthermore Haskell will always infer the most general type on a variable. So if you write, say, a sorting function without a type declaration, Haskell will make sure the function will work for all values that can be sorted.<br />
<br />
Compare how you would do this in certain object oriented languages. To gain polymorphism you would have to use some base class, and then declare your variables as instances of subclasses to this base class. It all amounts to tons of extra work and ridiculously complex declarations just to proclaim the existence of a variable. Furthermore you would have to perform tons of type conversions via explicit casts - definitely not a particularly elegant solution.<br />
If you want to write a polymorphic function in these object oriented languages you would probably declare the parameters as an object of a global base class (like "Object" in Java), which essentially allows the programmer to send anything into the function, even objects which can't logically be passed to the function. The end result is that most functions you write in these languages are not general, they only work on a single data type. You're also moving the error checking from compile-time to run-time. In large systems where some of the functionality is rarely used, these bugs might never be caught until they cause a fatal crash at the worst possible time.<br />
<br />
Haskell provides an elegant, concise and safe way to write your programs. Programs will not crash unexpectedly, nor produce strangely garbled output.<br />
<br />
===Elegance===<br />
Another property of Haskell that is very important to the programmer, even though it doesn't mean as much in terms of stability or performance, is the elegance of Haskell. To put it simply: stuff just works like you'd expect it to.<br />
<br />
To highlight the elegance of Haskell we shall now take a look at a small example. We choose QuickSort-inspired filtering sort because it's a simple algorithm that is actually useful. We will look at two versions - one written in C++, an imperative language, and one written in Haskell.<br />
Both versions use only the functionality available to the programmer without importing any extra modules (otherwise we could just call "sort" in each language's standard library and be done with it!). Thus, we use the standard sequence primitives of each language (a "list" in Haskell and an "array" in C++). Both versions must also be polymorphic (which is done "automatically" in Haskell, and with templates in C++). Both versions must use the same recursive algorithm.<br />
<br />
Please note that this is ''not'' intended as a definite comparison between the two languages. It's intended to show the elegance of Haskell, the C++ version is only included for comparison (and would be coded quite differently if you used the standard QuickSort algorithm or the Standard Template Libraries (STL), for example).<br />
<br />
template <typename T><br />
void qsort (T *result, T *list, int n)<br />
{<br />
if (n == 0) return;<br />
T *smallerList, *largerList;<br />
smallerList = new T[n];<br />
largerList = new T[n]; <br />
T pivot = list[0];<br />
int numSmaller=0, numLarger=0; <br />
for (int i = 1; i < n; i++)<br />
if (list[i] < pivot)<br />
smallerList[numSmaller++] = list[i];<br />
else <br />
largerList[numLarger++] = list[i];<br />
<br />
qsort(smallerList,smallerList,numSmaller); <br />
qsort(largerList,largerList,numLarger);<br />
<br />
int pos = 0; <br />
for ( int i = 0; i < numSmaller; i++)<br />
result[pos++] = smallerList[i];<br />
<br />
result[pos++] = pivot;<br />
<br />
for ( int i = 0; i < numLarger; i++)<br />
result[pos++] = largerList[i];<br />
<br />
delete [] smallerList;<br />
delete [] largerList;<br />
};<br />
<br />
We will not explain this code further, just note how complex and difficult it is to understand at a glance, largely due to the programmer having to deal with low-level details which have nothing to do with the task at hand.<br />
Now, let's take a look at a Haskell version of FilterSort, which might look a something like this.<br />
<br />
<haskell><br />
qsort [] = []<br />
qsort (x:xs) = qsort less ++ [x] ++ qsort more<br />
where less = filter (<x) xs<br />
more = filter (>=x) xs<br />
</haskell><br />
<br />
(This implementation has very poor runtime and space complexity, but that can be [http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html improved, at the expense of some of the elegance].)<br />
<br />
Let's dissect this code in detail, since it uses quite a lot of Haskell syntax that you might not be familiar with.<br />
The function is called qsort and takes a list as a parameter. We define a function in Haskell like so: funcname a b c = expr, where funcname is the name of the function, a, b, and, c are the parameters and expr is the expression to be evaluated (most often using the parameters). Functions are called by simply putting the function name first and then the parameter(s). Haskell doesn't use parenthesis for function application. Functions simply bind more tightly than anything else, so "f 5 * 2", for instance, would apply f to 5 and then multiply by 2, if we wanted the multiplication to occur before the function application then we would use parenthesis like so "f (5*2)".<br />
<br />
Let's get back to FilterSort.<br />
First we see that we have two definitions of the functions. This is called pattern matching and we can briefly say that it will test the argument passed to the function top-to-bottom and use the first one that matches.<br />
The first definition matches against [] which in Haskell is the empty list (a list of 1,2 and 3 is [1,2,3] so it makes sense that an empty list is just two brackets).<br />
So when we try to sort an empty list, the result will be an empty list. Sounds reasonable enough, doesn't it?<br />
The second definition pattern matches against a list with at least one element. It does this by using (x:xs) for its argument. The "cons" operator is (:) and it simply puts an element in front of a list, so that 0 : [1,2,3] returns [0,1,2,3]. Pattern matching against (x:xs) is a match against the list with the head x and the tail xs (which may or may not be the empty list). In other words, (x:xs) is a list of at least one element.<br />
So since we will need to use the head of the list later, we can actually extract this very elegantly by using pattern matching. You can think of it as naming the contents of the list. This can be done on any data construct, not just a list. It is possible to pattern match against an arbitrary variable name and then use the head function on that to retrieve the head of the list.<br />
Now if we have a non empty list, the sorted list is produced by sorting all elements that are smaller than x and putting that in front of x, then we sort all elements larger than x and put those at the end. We do this by using the list concatenation operator ++. Notice that x is not a list so the ++ operator won't work on it alone, which is why we make it a singleton-list by putting it inside brackets.<br />
So the function reads "To sort the list, sandwich the head between the sorted list of all elements smaller than the head, and the sorted list of all elements larger than the head". Which could very well be the original algorithm description. This is very common in Haskell. A function definition usually resembles the informal description of the function very closely. This is why I say that Haskell has a smaller semantic gap than other languages.<br />
<br />
But wait, we're not done yet! How is the list less and more computed? Well, remember that we don't care about sequencing in Haskell, so we've defined them below the function using the where notation (which allows any definitions to use the parameters of the function to which they belong). We use the standard prelude function filter, I won't elaborate too much on this now, but the line less = filter (<x) xs will use filter (<x) xs to filter the list xs. You can see that we actually pass the function which will be used to filter the list to filter, an example of higher order functions.<br />
The function (<x) should be read out "the function 'less than x'" and will return True if an element passed to it is less than x (notice how easy it was to construct a function on the fly, we put the expression "<x", "less than x", in parenthesis and sent it off to the function - functions really are just another value!).<br />
All elements that pass the test are output from the filter function and put inside less. In a same way (>=x) is used to filter the list for all elements larger than or equal to x.<br />
<br />
Now that you've had the syntax explained to you, read the function definition again. Notice how little time it takes to get an understanding about what the function does. The function definitions in Haskell explain what it computes, not how.<br />
<br />
If you've already forgotten the syntax outlined above, don't worry! We'll go through it more thoroughly and at a slower pace in the tutorials. The important thing to get from this code example is that Haskell code is elegant and intuitive.<br />
<br />
===Haskell and bugs===<br />
We have several times stated that various features of Haskell help fight the occurrence of bugs. Let's recap these.<br />
<br />
Haskell programs have fewer bugs because Haskell is:<br />
<br />
* '''Pure'''. There are no side effects.<br />
<br />
* '''Strongly typed'''. There can be no dubious use of types. And No Core Dumps!<br />
<br />
* '''Concise'''. Programs are shorter which make it easier to look at a function and "take it all in" at once, convincing yourself that it's correct.<br />
<br />
* '''High level'''. Haskell programs most often reads out almost exactly like the algorithm description. Which makes it easier to verify that the function does what the algorithm states. By coding at a higher level of abstraction, leaving the details to the compiler, there is less room for bugs to sneak in.<br />
<br />
* '''Memory managed'''. There's no worrying about dangling pointers, the Garbage Collector takes care of all that. The programmer can worry about implementing the algorithm, not book-keeping of the memory.<br />
<br />
* '''Modular'''. Haskell offers stronger and more "glue" to compose your program from already developed modules. Thus Haskell programs can be more modular. Often used modular functions can thus be proven correct by induction. Combining two functions that are proven to be correct, will also give the correct result (assuming the combination is correct).<br />
<br />
Furthermore most people agree that you just think differently when solving problems in a functional language. You subdivide the problem into smaller and smaller functions and then you write these small (and "almost-guaranteed-to-be-correct") functions, which are composed in various ways to the final result. There just isn't any room for bugs!<br />
<br />
<br />
== Haskell vs OOP ==<br />
The great benefit of Object Oriented Programming is rarely that you group your data with the functions that act upon it together into an object - it's that it allows for great data encapsulation (separating the interface from implementation) and polymorphism (letting a whole set of data types behave the same way). However:<br />
<br />
''Data encapsulation and polymorphism are not exclusive to OOP!''<br />
<br />
Haskell has tools for abstracting data. We can't really get into it without first going through the module system and how abstract data types (ADT) work in Haskell, something which is well beyond the scope of this essay. We will therefore settle for a short description of how ADTs and polymorphism works in Haskell.<br />
<br />
Data encapsulation is done in Haskell by declaring each data type in a separate module, from this module you only export the interface. Internally there might be a host of functions that touch the actual data, but the interface is all that's visible from outside of the module.<br />
Note that the data type and the functions that act upon the data type are not grouped into an "object", but they are (typically) grouped into the same module, so you can choose to only export certain functions (and not the constructors for the data type) thus making these functions the only way to manipulate the data type - "hiding" the implementation from the interface.<br />
<br />
Polymorphism is done by using something called type classes. Now, if you come from a C++ or Java background you might associate classes with something resembling a template for how to construct an object, but that's not what they mean in Haskell. A type class in Haskell is really just what it sounds like. It's a set of rules for determining whether a type is an instance of that class.<br />
So Haskell separates the class instantiation and the construction of the data type. You might declare a type "Porsche", to be an instance of the "Car" type class, say. All functions that can be applied onto any other member of the Car type class can then be applied to a Porsche as well.<br />
A class that's included with Haskell is the Show type class, for which a type can be instantiated by providing a show function, which converts the data type to a String. Consequently almost all types in Haskell can be printed onto the screen by applying show on them to convert them to a String, and then using the relevant IO action (more on IO in the tutorials).<br />
Note how similar this is to the the object notion in OOP when it comes to the polymorphism aspect.<br />
The Haskell system is a more intuitive system for handling polymorphism. You won't have to worry about inheriting in the correct hierarchical order or to make sure that the inheritance is even sensible. A class is just a class, and types that are instances of this class really doesn't have to share some parent-child inheritance relationship. If your data type fulfills the requirements of a class, then it can be instantiated in that class. Simple, isn't it?<br />
Remember the QuickSort example? Remember that I said it was polymorphic? The secret behind the polymorphism in qsort is that it is defined to work on any type in the Ord type class (for "Ordered"). Ord has a set of functions defined, among them is "<" and ">=" which are sufficient for our needs because we only need to know whether an element is smaller than x or not. So if we were to define the Ord functions for our Porsche type (it's sufficient to implement, say, <= and ==, Haskell will figure out the rest from those) in an instantiation of the Ord type class, we could then use qsort to sort lists of Porsches (even though sorting Porsches might not make sense).<br />
Note that we never say anything about which classes the elements of the list must be defined for, Haskell will infer this automatically from just looking at which functions we have used (in the qsort example, only "<" and ">=" are relevant).<br />
<br />
So to summarize: Haskell does include mechanisms for data encapsulation that match or surpass those of OOP languages. The only thing Haskell does not provide is a way to group functions and data together into a single "object" (aside from creating a data type which includes a function - remember, functions are data!). This is, however, a very minor problem. To apply a function to an object you would write "func obj a b c" instead of something like "obj.func a b c".<br />
<br />
<br />
== Modularity ==<br />
A central concept in computing is modularity. A popular analogy is this: say you wanted to construct a wooden chair. If you construct the parts of it separately, and then glue them together, the task is solved easily. But if you were to carve the whole thing out of a solid piece of wood, it would prove to be quite a bit harder. John Hughes had this to say on the topic in his paper [http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters]<br />
<br />
''"Languages which aim to improve productivity must support modular programming well. But new scope rules and mechanisms for separate compilation are not enough - modularity means more than modules. Our ability to decompose a problem into parts depends directly on our ability to glue solutions together. To assist modular programming, a language must provide good glue.''<br />
<br />
''Functional programming languages provide two new kinds of glue - higher-order functions and lazy evaluation."''<br />
<br />
<br />
==The speed of Haskell ==<br />
Let me first state clearly that the following only applies to the general case in which speed isn't absolutely critical, where you can accept a few percent longer execution time for the benefit of reducing development time greatly. There are cases when speed is the primary concern, and then the following section will not apply to the same extent.<br />
<br />
Now, some C++ programmers might claim that the C++ version of QuickSort above is probably a bit faster than the Haskell version. And this might be true. For most applications, though, the difference in speed is so small that it's utterly irrelevant. For instance, take a look at the [http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=all Computer Language Benchmarks Game], where Haskell compares favorably to most of the so called "fast" languages.<br />
Now, these benchmarks don't prove all that much about real-world performance, but they do show that Haskell isn't as slow as some people think. At the time of writing it's in 4th position, only slightly behind C and C++.<br />
<br />
Almost all programs in use today have a fairly even spread of processing time among its functions. The most notable exceptions are applications like MPEG encoders, and artificial benchmarks, which spend a large portion of their execution time within a small portion of the code. If you ''really'' need speed at all costs, consider using C instead of Haskell.<br />
<br />
There's an old rule in computer programming called the "80/20 rule". It states that 80% of the time is spent in 20% of the code. The consequence of this is that any given function in your system will likely be of minimal importance when it comes to optimizations for speed. There may be only a handful of functions important enough to optimize. These important functions could be written in C (using the excellent foreign function interface in Haskell). The role of C could, and probably will, take over the role of assembler programming - you use it for the really time-critical bits of your system, but not for the whole system itself.<br />
<br />
We should continue to move to higher levels of abstraction, just like we've done before. We should trade application speed for increased productivity, stability and maintainability. Programmer time is almost always more expensive than CPU time.<br />
We aren't writing applications in assembler anymore for the same reason we shouldn't be writing applications in C anymore.<br />
<br />
Finally remember that algorithmic optimization can give much better results than code optimization. For theoretical examples when factors such as development times and stability doesn't matter, then sure, C is often faster than Haskell. But in the real world development times ''do'' matter, this isn't the case. If you can develop your Haskell application in one tenth the time it would take to develop it in C (from experience, this is not at all uncommon) you will have lots of time to profile and implement new algorithims. So in the "real world" where we don't have infinite amounts of time to program our applications, Haskell programs can often be much faster than C programs.<br />
<br />
== Epilogue ==<br />
So if Haskell is so great, how come it isn't "mainstream"? Well, one reason is that the operating system is probably written in C or some other imperative language, so if your application mainly interacts with the internals of the OS, you may have an easier time using imperative languages. Another reason for the lack of Haskell, and other functional languages, in mainstream use is that programming languages are rarely thought of as tools (even though they are). To most people their favorite programming language is much more like religion - it just seems unlikely that any other language exists that can get the job done better and faster.<br />
<br />
There is an essay by Paul Graham called [http://www.paulgraham.com/avg.html Beating the Averages] describing his experience using Common Lisp, another functional language, for an upstart company. In it he uses an analogy which he calls "The Blub Paradox".<br />
<br />
It goes a little something like this:<br />
If a programmer's favorite language is Blub, which is positioned somewhere in the middle of the "power spectrum", he can most often only identify languages that are lower down in the spectrum. He can look at COBOL and say "How can anyone get anything done in that language, it doesn't have feature x", x being a feature in Blub.<br />
<br />
However, this Blub programmer has a harder time looking the other way in the spectrum. If he examines languages that are higher up in the power spectrum, they will just seem "weird" because the Blub programmer is "thinking in Blub" and can not possibly see the uses for various features of more powerful languages. It goes without saying that this inductively leads to the conclusion that to be able to compare all languages you'll need to position yourself at the top of the power spectrum. It is my belief that functional languages, almost by definition, are closer to the top of the power spectrum than imperative ones.<br />
So languages can actually limit a programmers frame of thought. If all you've ever programmed is Blub, you may not see the limitations of Blub - you may only do that by switching to another level which is more powerful.<br />
<br />
One of the reasons the mainstream doesn't use Haskell is because people feel that "their" language does "everything they need". And of course it does, because they are thinking in Blub! Languages aren't just technology, it's a way of thinking. And if you're not thinking in Haskell, it is very hard to see the use of Haskell - even if Haskell would allow you to write better applications in a shorter amount of time!<br />
<br />
Hopefully this article has helped you break out of the Blub paradox. Even though you may not yet "think in Haskell", it is my hope that you are at least aware of any limitations in your frame of thought imposed by your current "favorite" language, and that you now have more motivation to expand it by learning something new.<br />
<br />
If you are committed to learn a functional language, to get a better view of the power spectrum, then Haskell is an excellent candidate.<br />
<br />
[[Category:Tutorials]]</div>Drbbhttps://wiki.haskell.org/index.php?title=Talk:Why_Haskell_matters&diff=43805Talk:Why Haskell matters2012-01-04T05:49:21Z<p>Drbb: QuickSort debunk</p>
<hr />
<div>I wikified my old article for easier modification by the community (up until now people had to email me and then i would upload a new version -- time consuming!)<br />
--[[User:SebastianSylvan|SebastianSylvan]] 06:48, 9 January 2006 (EST)<br />
<br />
Hopefully I'm preaching to the choir here, but I'd just like to clarify that I'm perfectly fine with, and actively encourage, large-scale editing of this (I wouldn't put it on the wiki otherwise!). Just because it at one point was a stand-alone article with me as the author doesn't mean it shouldn't be substantially modified. For instance, the speed-section could be updated with some references to the language shootout, removing some pointless bits, etc. So go nuts! --[[User:SebastianSylvan|SebastianSylvan]] 13:55, 22 January 2006 (UTC)<br />
<br />
<br />
On the page it refers to Haskell's speed being better than C++ and provides a link to the programming language shootout. I don't find that when I go there. Has something changed? I'd like to see benchmarks where Haskell has performed that well, but I haven't found any. Please let me know --[[User:Kylebutt|Kylebutt]] 06:26, 3 February 2007 (UTC)<br />
<br />
Kyle, sorry that this is over a year after your question... but I think it means the development speed: It takes a fraction of the time to develop in Haskell.<br />
Also, the shootout shows Haskell performing very well on multi-core systems. Not quite to pace with C, but barely behind. Cheers.<br />
[[User:Cknapp|Cknapp]] 17:01, 25 November 2008 (UTC)<br />
<br />
----<br />
<br />
(Edit: To give this section some context, I found this page while looking for a good introduction to entice someone into trying Haskell. Unfortunately, the content of this page was such that I could not pass it on to them in good faith.)<br />
<br />
There are numerous untrue and/or ridiculous claims on this page.<br />
<br />
1. "In Haskell, the sequencing task is removed. You only care what the program is to compute not how or when it is computed."<br />
<br />
This is clearly not true. Maybe it is "often true", but that's not the same thing.<br />
<br />
2. You wouldn't expect "4 = 5" to be a valid assignment in any language, so it's really quite strange that "x = 4; x = 5" is.<br />
<br />
If you replace "=" with "<-", does the claim still hold? Oh wait, that's Haskell's "do" syntax. This is an argument about syntax trivialities, not anything substantial.<br />
<br />
3. "Furthermore Haskell doesn't allow side-effects, which leads to less bugs."<br />
<br />
But it does; they just happen in the IO monad. OpenGL programming isn't magically safer in Haskell than in C++; or, at least, not for this reason alone.<br />
<br />
4. "You could argue that Haskell has a much better form of duck typing."<br />
<br />
No you can't. You'd need some form of structural record types at a minimum. That's not to say you can't solve the problem another way, but the way you're solving it definitely won't be via duck typing.<br />
<br />
5. "Furthermore Haskell will always infer the most general type on a variable."<br />
<br />
No it won't, but I can let this one go.<br />
<br />
6. "It all amounts to tons of extra work and ridiculously complex declarations just to proclaim the existence of a variable. Furthermore you would have to perform tons of type conversions via explicit casts - definitely not a particularly elegant solution."<br />
<br />
This sounds more like a criticism of Java than OOP. I suppose that's why Java is used as an example later in the paragraph.<br />
<br />
7. "Programs will not crash unexpectedly, nor produce strangely garbled output."<br />
<br />
Yes they will. Maybe less often, but this claim is far too bold.<br />
<br />
8. "Haskell does include mechanisms for data encapsulation that match or surpass those of OOP languages."<br />
<br />
This whole section is bogus. Neither abstract data types implemented via the module system nor type classes provide the sort of open recursion and dynamic dispatch that you get in an OO language. You can get most of the way there with existentials/GADTs but they aren't mentioned at all in the paragraph (nor are they standard Haskell). Haskell also lacks the subtyping found in virtually all typed OO languages. See http://userweb.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf.<br />
<br />
[[User:Johnnowak|Johnnowak]] 01:23, 15 April 2010 (UTC)<br />
<br />
<br />
In addition to the problems Johnnowak mentions, the QuickSort example code is extremely misleading.<br />
<br />
1. First off, it's not quicksort. See http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html <br />
<br />
2. Second, on my machine, the Haskell version runs in 10x the runtime and 8x the RAM of the C++ version, a key performance point not mentioned in the text. <br />
<br />
3. Third, even laying aside whether the sort is officially "quicksort", and allowing this "Haskell sort" as an illustration, it's important to note that the actual standard quicksort is much simpler to write in C++ than the version shown here. The standard implementation is also even faster (by another factor of 5x, for 50x total) and has lower memory footprint.<br />
(http://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort)<br />
<br />
In fact, you can write a standard quicksort in Haskell (as shown on Augustss's blog), and it turns out to have about the same performance and code complexity as the C++ version.<br />
<br />
So, all the example seems to show is that Haskell makes it easy to write slow, heavy programs. Which is nice (and competitive with scripting languages, maybe), but not at all the point the article is trying to make.<br />
<br />
<br />
[[User:Drbb|Drbb]] 05:49, 4 January 2012 (UTC)</div>Drbb