https://wiki.haskell.org/api.php?action=feedcontributions&user=PhilipNeustrom&feedformat=atomHaskellWiki - User contributions [en]2024-03-19T10:59:16ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Applications_and_libraries/Graphics&diff=22114Applications and libraries/Graphics2008-08-03T20:22:01Z<p>PhilipNeustrom: GD</p>
<hr />
<div>Dealing with graphics, drawing and graphics file formats. For information about libraries for graphical user interfaces, see [[Libraries and tools/GUI libraries|GUI libraries]].<br />
<br />
== Applications ==<br />
<br />
;[http://haskell.org/Blobs Blobs diagram editor]<br />
:Blobs is a diagram editor for directed graphs. It is written in Haskell, using the platform-independent GUI toolkit wxHaskell. Blobs is a front-end for drawing and editing graph diagrams.<br />
<br />
;[http://web.comlab.ox.ac.uk/oucl/work/ian.lynagh/Fraskell/ Fraskell]<br />
:A Haskell program that generates images of the Mandelbrot set.<br />
<br />
=== Ray tracing ===<br />
<br />
;[http://www.cse.unsw.edu.au/~cgray/banky/ Banky : Monte Carlo ray tracing]<br />
:A monte carlo ray tracer in Haskell. Monte-Carlo ray-Tracing uses random and quasi-random techniques for improved image synthesis. Monte-carlo ray-tracers simulate global illumination and eliminates the ambient term. It does this using a set of random techniques to simulate an integration model of illumination, which is far more realistic.<br />
<br />
;[http://www.haskell.org/tmrwiki/HRay HRay: A Haskell ray tracer]<br />
:HRay, a ray tracer in Haskell. The goal is to show how elegant, short and maintainable a ray tracing implementation would be in a functional language, as opposed to an imperative or procedural language. It uses a formal model for the application, using the functional and declarative formalism Funmath <br />
<br />
;[http://staff.science.uva.nl/~kort/hart/index.html HaRT: Haskell ray tracer]<br />
:Yet another Haskell ray tracer<br />
<br />
;[http://benny.kramekweb.com/hrayt/ hrayt, A Haskell Raytracer]<br />
:A Haskell ray tracer in only a few hours.<br />
<br />
;[http://www.nobugs.org/developer/htrace/index.html Htrace, A Haskell Raytracer]<br />
:A 1 day raytracer.<br />
<br />
;[http://www.xs4all.nl/~jkort/ Haskell Ray Tracer]<br />
:A Haskell ray tracer written for Jan Kort's master thesis<br />
<br />
;[http://www.cs.mu.oz.au/~bjpop/code.html bjpop-ray]<br />
:A simple raytracer using wxHaskell for the GUI.<br />
<br />
;[http://groups.csail.mit.edu/graphics/classes/6.837/F99/projects/reports/team06.pdf Parallel Ray Tracing in pH]<br />
:A parallel ray tracer, using the parallel Haskell<br />
<br />
;Galois Ray Tracer from icfp00<br />
:A Galois Connections team submitted a ray tracer entry in Haskell in the 2000 icfp contest<br />
<br />
;[http://www.macs.hw.ac.uk/~gnik/apset/ray_tracer.lhs A Ray Tracer for Spheres]<br />
:David King's Haskell port of an Id ray tracer from the [http://www.csg.lcs.mit.edu/impala/ Impala suite]<br />
<br />
;[http://syn.cs.pdx.edu/~jsnow/glome Glome]<br />
:A ray tracer written by Jim Snow with a modern acceleration structure and a variety primitive types.<br />
<br />
== Libraries ==<br />
<br />
;[http://haskell.org/graphics/ The Hugs Graphics Library]<br />
:The Hugs Graphics Library supports 2-dimensional graphics operations, timers, mouse and keyboard actions and multiple windows. It runs on Hugs under both Win32 and X11. An earlier version was used for early prototypes of Fran.<br />
<br />
;[http://haskell.org/haven/ Haven]<br />
:Scalable Vector Graphics for Haskell. Portable, device-independent, resolution-independent library, including support for affine transformations, Bezier curves, fine-grained control of pen attributes, bounds and intersection tests, constructive area geometry, anti-aliased rendering, outline fonts, etc.<br />
<br />
;[http://www.conal.net/Fran/ Functional Reactive Animation]<br />
:FRAN is a Haskell library (or "embedded language") for interactive animations with 2D and 3D graphics and sound. It runs on Hugs under Windows 95 and Windows NT, using Win32 graphics (GDI).<br />
<br />
;[[Grapefruit]]<br />
:Grapefruit is a library for programming graphical animations and GUIs in a declarative way. It is based on the concepts of [[Functional Reactive Programming]].<br />
<br />
;[http://haskell.org/HOpenGL/ HOpenGL]<br />
:HOpenGL is a Haskell binding for the OpenGL graphics API (GL 2.1 / GLU 1.3) and the portable OpenGL utility toolkit GLUT.<br />
<br />
;[http://cryp.to/funcmp/ Functional Metapost]<br />
:Functional Metapost is a Haskell binding for MetaPost, the powerful but cumbersome graphics language.<br />
<br />
;[http://www.haskell.org/haskellwiki/HaskLS L-systems]<br />
:A Haskell implementation for Lindenmayer Systems (L-systems). The goal is to implement L-systems in Haskell, and provide a way to visualize them using HOpenGL.<br />
<br />
;[http://darcs.haskell.org/~lemmih/hsSDL/ hsSDL]<br />
:Contains bindings to libSDL, libSDL_gfx, libSDL_image, libSDL_mixer and libSDL_ttf.<br />
<br />
;[http://dockerz.net/software/chart.html Chart Library]<br />
: A simple library for drawing 2D charts, implemented in haskell, using the [http://cairographics.org/ Cairo] graphics library for rendering.<br />
<br />
;[http://linuz.sns.it/~monge/wiki/index.php/Milfoh Milfoh]<br />
:An image to texture loading library. Use SDL_image (and a bare minimun of SDL), to load image files as opengl textures.<br />
<br />
;[http://users.info.unicaen.fr/~karczma/Work/Clastic_distr/clastic.html Clastic]<br />
:Texture generation<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/gd-3000.0.1 GD bindings]: Bindings to a small subset of the GD graphics library.<br />
<br />
=== Pan ===<br />
<br />
;[http://www.conal.net/pan Pan]<br />
:An embedded language and highly optimizing compiler for image synthesis and transformation, based on the simple idea of images as functions over infinite, continuous 2D space. The resulting binaries can be used as PhotoShop plugins, embedded in web pages or PowerPoint, or used in an interactive standalone viewer. The compiler contains no domain-specific knowledge, so it's very extensible. See the [http://www.conal.net/pan/Gallery/ gallery] for visual examples. Currently Windows-only, but ports are encouraged.<br />
<br />
;[http://haskell.org/edsl/pansharp.html Pan#]<br />
:Pan# is a slightly re-engineered version of Pan. It uses the same compiler but used the Microsoft .NET framework instead of visual studio, making it easier to install and use. It also has a number of new features added. While Pan is embedded in Haskell, Pan# has its own Haskell-like language built in so there is no need to use other Haskell compilers. Currently Windows-only.<br />
<br />
;[http://www.acooke.org/jara/pancito/index.html Pancito]<br />
:Pancito is a Haskell module for manipulating functional images and then saving them to disk. It was inspired by Pan.<br />
<br />
;[http://www.cse.unsw.edu.au/~sseefried/pan/index.html Panic]<br />
:A cross-platform re-implementation of Pan in Haskell using the wxWidgets GUI library and OpenGL graphics library.<br />
<br />
=== Graphics file formats ===<br />
<br />
;[http://www.alpheccar.org/en/posts/show/82 HPDF]<br />
:A small portable Haskell library to generate PDF pictures.<br />
<br />
;[http://www.cs.uu.nl/people/jeroen/ Functional Specification of the JPEG algorithm], and an Implementation for Free<br />
<br />
;[http://web.archive.org/web/20010606145143/www.numeric-quest.com/haskell/gd/index.html PNG and JPEG writer]<br />
: available at internet archive; cumbersome for download<br />
<br />
;[http://web.archive.org/web/20010306041706/www.numeric-quest.com/funpdf/index.html PDF writer]<br />
: available at internet archive; cumbersome for download<br />
<br />
<br />
<br />
{{LibrariesPage}}</div>PhilipNeustromhttps://wiki.haskell.org/index.php?title=Weekly_Meeting&diff=22048Weekly Meeting2008-07-30T23:32:31Z<p>PhilipNeustrom: fixed link</p>
<hr />
<div>Many GHC users have recently been coordinating on a time to meet on IRC to discuss topics of interest to the compiler community. This is an informal gathering to exchange ideas and views on any current issues.<br />
<br />
'''When''': Wednesdays, 0800 PDT / 1100h EDT / 1600 BST<br />
<br />
'''Where''': irc.freenode.net #ghc<br />
<br />
Note: the meeting is in #ghc, and whilst the topics sometimes stray outside of just GHC, we would like to keep the agenda as close to GHC-only as possible<br />
<br />
=== Agenda ===<br />
If you desire to discuss a particular topic then post it here and perhaps shoot out an e-mail so people can give it proper thought and show up with something to contribute.<br />
<br />
NONE YET<br />
<br />
=== Recent History ===<br />
* July 23: Should the GHC repo switch to a [http://hackage.haskell.org/trac/ghc/wiki/DarcsEvaluation different DRCS] (i.e. leave Darcs)? <br />
* July 16: The [[Haskell Platform]] was discussed including which libraries to include initially, criteria, and development process.<br />
<br />
== Logs ==<br />
IRC logs can be found on the GHC wiki[http://hackage.haskell.org/trac/ghc/wiki/IRC_Meetings].</div>PhilipNeustromhttps://wiki.haskell.org/index.php?title=UTF-8&diff=21886UTF-82008-07-22T02:22:15Z<p>PhilipNeustrom: question - what about other string encodings?</p>
<hr />
<div>[[Category:Code]]<br />
<br />
The simplest solution seems to be to use the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/utf8-string utf8-string package] from Galois. It <br />
provides a drop-in replacement for System.IO<br />
<br />
''What about other string encodings?''<br />
<br />
== Example ==<br />
If we use a function from System.IO.UTF8, we should also hide the equivalent one from the Prelude. (Alternatively, we could import the UTF8 module qualified)<br />
<br />
<haskell><br />
> import System.IO.UTF8<br />
> import Prelude hiding (readFile, writeFile)<br />
> import System.Environment (getArgs)<br />
</haskell><br />
<br />
The readFile and writeFile functions are the same as before...<br />
<br />
<haskell><br />
> main :: IO ()<br />
> main =<br />
> do args <- getArgs<br />
> mapM_ reverseUTF8File args<br />
<br />
> reverseUTF8File :: FilePath -> IO ()<br />
> reverseUTF8File f =<br />
> do c <- readFile f<br />
> writeFile (f ++ ".rev") $ reverseLines c<br />
> where<br />
> reverseLines = unlines . map reverse . lines<br />
</haskell></div>PhilipNeustromhttps://wiki.haskell.org/index.php?title=State_Monad&diff=21256State Monad2008-06-09T23:44:55Z<p>PhilipNeustrom: unless i'm mistaken.. i think there are other type mistakes here?</p>
<hr />
<div>The State Monad by Example<br />
<br />
This is a short tutorial on the state monad. Emphasis is placed on intuition. The types have been simplified to protect the innocent.<br />
<br />
<br />
=Foundations=<br />
==Primitives==<br />
<br />
<haskell><br />
runState (return 'X') 1<br />
</haskell><br />
<blockquote><br />
('X',1)<br />
</blockquote><br />
<br />
Return set the result value but left the state unchanged.<br />
Comments:<br />
return 'X' :: State Int Char<br />
runState (return 'X') :: Int -> (Char, Int)<br />
initial state = 1 :: Int<br />
final value = 'X' :: Char<br />
final state = 1 :: Int<br />
result = ('X', 1) :: (Char, Int)<br />
<br />
----<br />
<haskell><br />
runState get 1<br />
</haskell><br />
<blockquote><br />
(1,1)<br />
</blockquote><br />
<br />
Get set the result value to the state and left the state unchanged.<br />
Comments:<br />
get :: State Int Int<br />
runState get :: Int -> (Int, Int)<br />
initial state = 1 :: Int<br />
final value = 1 :: Int<br />
final state = 1 :: Int<br />
<br />
<br />
----<br />
<haskell><br />
runState (put 5) 1<br />
</haskell><br />
<blockquote><br />
((),5)<br />
</blockquote><br />
<br />
Put set the result value to () and set the state value.<br />
Comments:<br />
put 5 :: State Int ()<br />
runState (put 5) :: Int -> ((),Int)<br />
initial state = 1 :: Int<br />
final value = () :: ()<br />
final state = 5 :: Int<br />
<br />
==Combinations==<br />
<br />
Because (State s) forms a monad, values can be combined together with (>>=) or do{}.<br />
<br />
<haskell><br />
runState (do { put 5; return 'X' }) 1<br />
</haskell><br />
<blockquote><br />
('X',5)<br />
</blockquote><br />
Comments:<br />
do { put 5; return 'X' } :: State Int Char <br />
runState (do { put 5; return 'X' }) :: Int -> (Char,Int)<br />
initial state = 1 :: Int<br />
final value = 'X' :: Char<br />
final state = 5 :: Int<br />
<br />
<br />
----<br />
<haskell><br />
postincrement = do { x <- get; put (x+1); return x }<br />
runState postincrement 1<br />
</haskell><br />
<blockquote><br />
(1,2)<br />
</blockquote><br />
<br />
----<br />
<haskell><br />
predecriment = do { x <- get; put (x-1); get }<br />
runState predecriment 1<br />
</haskell><br />
<blockquote><br />
(0,0)<br />
</blockquote><br />
<br />
==Other Functions==<br />
<haskell><br />
runState (modify (+1)) 1<br />
</haskell><br />
<blockquote><br />
((),2)<br />
</blockquote><br />
<br />
----<br />
<haskell><br />
runState (gets (+1)) 1<br />
</haskell><br />
<blockquote><br />
(2,1)<br />
</blockquote><br />
<br />
----<br />
<haskell><br />
evalState (gets (+1)) 1<br />
</haskell><br />
<blockquote><br />
2<br />
</blockquote><br />
<br />
----<br />
<haskell><br />
execState (gets (+1)) 1<br />
</haskell><br />
<blockquote><br />
1<br />
</blockquote><br />
<br />
=Implementation=<br />
<br />
At its heart, a value of type (State s a) is a function from initial state s to final value a and final state s: (a,s). These are usually wrapped, but shown here unwrapped for simplicity.<br />
<br />
Return leaves the state unchanged and sets the result:<br />
<haskell><br />
-- ie: (return 5) 1 -> (5,1)<br />
return :: a -> State s a<br />
return x s = (x,s)<br />
</haskell><br />
<br />
Get leaves state unchanged and sets the result to the state:<br />
<haskell><br />
-- ie: get 1 -> (1,1)<br />
get :: State s s<br />
get s = (s,s)<br />
</haskell><br />
<br />
Put sets the result to () and sets the state:<br />
<haskell><br />
-- ie: (put 5) 1 -> ((),5)<br />
put :: s -> State s ()<br />
put x s = ((),x)<br />
</haskell><br />
<br />
----<br />
The helpers are simple variations of these primitives:<br />
<haskell><br />
modify :: (s -> s) -> State s ()<br />
modify f = do { x <- get; put (f x) }<br />
<br />
gets :: (s -> a) -> State s a<br />
gets f = do { x <- get; return (f x) }<br />
</haskell><br />
<br />
EvalState and execState just select one of the two values returned by runState. EvalState returns the final result while execState returns the final state:<br />
<haskell><br />
evalState :: State s a -> s -> a<br />
evalState act = fst $ runState act<br />
<br />
execState :: State s a -> s -> s<br />
execState act = snd $ runState act<br />
</haskell><br />
<br />
----<br />
Combining two states is the trickiest bit in the whole scheme. To combine do { x <- act1; act2 x } we need a function which takes an initial state, runs act1 to get an intermediate result and state, feeds the intermediate result to act2 and then runs that action with the intermediate state to get a final result and a final state:<br />
<br />
<haskell><br />
(>>=) :: State s a -> (a -> State s b) -> State s b<br />
(act1 >>= fact2) s = runState act2 is <br />
where (iv,is) = runState act1 s<br />
act2 = fact2 iv<br />
</haskell><br />
<br />
[[Category:Tutorials]]</div>PhilipNeustromhttps://wiki.haskell.org/index.php?title=Introduction_to_QuickCheck1&diff=20661Introduction to QuickCheck12008-04-22T03:04:53Z<p>PhilipNeustrom: linked quickcheck w/ ghc batch script, caught me up for a bit</p>
<hr />
<div>A quick introduction to QuickCheck, and testing Haskell code.<br />
<br />
== Motivation ==<br />
<br />
In September 2006, Bruno MartÃnez<br />
[http://www.haskell.org/pipermail/haskell-cafe/2006-September/018302.html asked] <br />
the following question:<br />
<br />
<haskell><br />
-- I've written a function that looks similar to this one<br />
<br />
getList = find 5 where<br />
find 0 = return []<br />
find n = do<br />
ch <- getChar<br />
if ch `elem` ['a'..'e'] then do<br />
tl <- find (n-1)<br />
return (ch : tl) else<br />
find n<br />
<br />
-- I want to test this function, without hitting the filesystem. In C++ I<br />
-- would use a istringstream. I couldn't find a function that returns a<br />
-- Handle from a String. The closer thing that may work that I could find<br />
-- was making a pipe and convertind the file descriptor. Can I simplify<br />
-- that function to take it out of the IO monad?<br />
</haskell><br />
<br />
So the problem is: how to effectively test this function in Haskell? The<br />
solution we turn to is refactoring and QuickCheck.<br />
<br />
== Keeping things pure ==<br />
<br />
The reason your getList is hard to test, is that the side effecting monadic code <br />
is mixed in with the pure computation, making it difficult to test<br />
without moving entirely into a "black box" IO-based testing model.<br />
Such a mixture is not good for reasoning about code.<br />
<br />
Let's untangle that, and then test the referentially transparent<br />
parts simply with QuickCheck. We can take advantage of lazy IO firstly,<br />
to avoid all the unpleasant low-level IO handling. <br />
<br />
So the first step is to factor out the IO part of the function into a<br />
thin "skin" layer:<br />
<br />
<haskell><br />
-- A thin monadic skin layer<br />
getList :: IO [Char]<br />
getList = fmap take5 getContents<br />
<br />
-- The actual worker<br />
take5 :: [Char] -> [Char]<br />
take5 = take 5 . filter (`elem` ['a'..'e'])<br />
</haskell><br />
<br />
== Testing with QuickCheck ==<br />
<br />
Now we can test the 'guts' of the algorithm, the take5 function, in<br />
isolation. Let's use QuickCheck. First we need an Arbitrary instance for<br />
the Char type -- this takes care of generating random Chars for us to<br />
test with. I'll restrict it to a range of nice chars just for<br />
simplicity:<br />
<br />
<haskell><br />
import Data.Char<br />
import Test.QuickCheck<br />
<br />
instance Arbitrary Char where<br />
arbitrary = choose ('\32', '\128')<br />
coarbitrary c = variant (ord c `rem` 4)<br />
</haskell><br />
<br />
Let's fire up GHCi (or Hugs) and try some generic properties (its nice<br />
that we can use the QuickCheck testing framework directly from the<br />
Haskell prompt). An easy one first, a [Char] is equal to itself:<br />
<br />
<haskell><br />
*A> quickCheck ((\s -> s == s) :: [Char] -> Bool)<br />
OK, passed 100 tests.<br />
</haskell><br />
<br />
What just happened? QuickCheck generated 100 random [Char] values, and<br />
applied our property, checking the result was True for all cases.<br />
QuickCheck ''generated the test sets for us''!<br />
<br />
A more interesting property now: reversing twice is the identity:<br />
<br />
<haskell><br />
*A> quickCheck ((\s -> (reverse.reverse) s == s) :: [Char] -> Bool)<br />
OK, passed 100 tests.<br />
</haskell><br />
<br />
Great!<br />
<br />
== Testing take5 ==<br />
<br />
The first step to testing with QuickCheck is to work out some properties<br />
that are true of the function, for all inputs. That is, we need to find<br />
''invariants''.<br />
<br />
A simple invariant might be:<br />
<math>\forall~s~.~length~(take5~s)~=~5</math><br />
<br />
So let's write that as a QuickCheck property:<br />
<haskell><br />
\s -> length (take5 s) == 5<br />
</haskell><br />
<br />
Which we can then run in QuickCheck as:<br />
<haskell><br />
*A> quickCheck (\s -> length (take5 s) == 5)<br />
Falsifiable, after 0 tests:<br />
""<br />
</haskell><br />
<br />
Ah! QuickCheck caught us out. If the input string contains less than 5<br />
filterable characters, the resulting string will be less than 5<br />
characters long. So let's weaken the property a bit:<br />
<math>\forall~s~.~length~(take5~s)~\le~5</math><br />
<br />
That is, take5 returns a string of at most 5 characters long. Let's test<br />
this: <br />
<haskell><br />
*A> quickCheck (\s -> length (take5 s) <= 5)<br />
OK, passed 100 tests.<br />
</haskell><br />
<br />
Good!<br />
<br />
== Another property ==<br />
<br />
Another thing to check would be that the correct characters are<br />
returned. That is, for all returned characters, those characters are<br />
members of the set ['a','b','c','d','e'].<br />
<br />
We can specify that as:<br />
<math>\forall~s~.~\forall~e~.~e~\in~take5~s~\to~e~\in~[abcde] </math><br />
<br />
And in QuickCheck:<br />
<haskell><br />
*A> quickCheck (\s -> all (`elem` ['a'..'e']) (take5 s))<br />
OK, passed 100 tests.<br />
</haskell><br />
<br />
Excellent. So we can have some confidence that the function neither<br />
returns strings that are too long, nor includes invalid characters.<br />
<br />
== Coverage ==<br />
<br />
One issue with the default QuickCheck configuration, when testing<br />
[Char], is that the standard 100 tests isn't enough for our situation.<br />
In fact, QuickCheck never generates a String greater than 5 characters<br />
long, when using the supplied Arbtrary instance for Char! We can confirm<br />
this:<br />
<br />
<haskell><br />
*A> quickCheck (\s -> length (take5 s) < 5)<br />
OK, passed 100 tests.<br />
</haskell><br />
<br />
QuickCheck wastes its time generating different Chars, when what we<br />
really need is longer strings. One solution to this is to modify<br />
QuickCheck's default configuration to test deeper:<br />
<br />
<haskell><br />
deepCheck p = check (defaultConfig { configMaxTest = 10000}) p<br />
</haskell><br />
<br />
This instructs the system to find at least 10000 test cases before<br />
concluding that all is well. Let's check that it is generating longer<br />
strings:<br />
<br />
<haskell><br />
*A> deepCheck (\s -> length (take5 s) < 5)<br />
Falsifiable, after 125 tests:<br />
";:iD^*NNi~Y\\RegMob\DEL@krsx/=dcf7kub|EQi\DELD*"<br />
</haskell><br />
<br />
We can check the test data QuickCheck is generating using the<br />
'verboseCheck' hook. Here, testing on integers lists:<br />
<br />
<haskell><br />
*A> verboseCheck (\s -> length s < 5)<br />
0: []<br />
1: [0]<br />
2: []<br />
3: []<br />
4: []<br />
5: [1,2,1,1]<br />
6: [2]<br />
7: [-2,4,-4,0,0]<br />
Falsifiable, after 7 tests:<br />
[-2,4,-4,0,0]<br />
</haskell><br />
<br />
== Going further ==<br />
<br />
QuickCheck is effectively an embedded domain specific language for<br />
testing Haskell code, and allows for much more complex properties than<br />
those you've seen here to be tested. Some sources for further reading<br />
are:<br />
* [http://www.cse.unsw.edu.au/~dons/data/QuickCheck.html The QuickCheck source]<br />
** [http://mathburritos.org/code/darcsweb/browse?r=ghcQC;a=summary QuickCheck GHC batch script]<br />
* [http://haskell.org/ghc/docs/latest/html/libraries/QuickCheck/Test-QuickCheck.html Library documentation]<br />
* [http://www.cse.unsw.edu.au/~dons/code/fps/tests/Properties.hs A large testsuite of QuickCheck code]<br />
* [http://www.cs.chalmers.se/~rjmh/QuickCheck/manual.html QuickCheck Manual]<br />
* Paper [http://www.cs.chalmers.se/~koen/pubs/icfp00-quickcheck.ps QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs], Koen Claessen and John Hughes. In Proc. of International Conference on Functional Programming (ICFP), ACM SIGPLAN, 2000.<br />
* Paper [http://www.math.chalmers.se/~koen/pubs/entry-fop-quickcheck.html Specification Based Testing with QuickCheck], Koen Claessen and John Hughes. In Jeremy Gibbons and Oege de Moor (eds.), The Fun of Programming, Cornerstones of Computing, pp. 17--40, Palgrave, 2003.<br />
* Paper [http://www.math.chalmers.se/~koen/pubs/entry-tt04-quickcheck.html QuickCheck: Specification-based Random Testing], Koen Claessen. Presentation at Summer Institute on Trends in Testing: Theory, Techniques and Tools, August 2004.<br />
* Paper [http://www.cs.chalmers.se/~rjmh/Papers/QuickCheckST.ps Testing Monadic Programs with QuickCheck], Koen Claessen, John Hughes. SIGPLAN Notices 37(12): 47-59 (2002):<br />
* More [http://haskell.org/haskellwiki/Research_papers/Testing_and_correctness research on correctness and testing] in Haskell<br />
* Tutorial: [[QuickCheck as a test set generator]]<br />
* Tutorial: [[QuickCheck / GADT]]<br />
<br />
Note, QuickCheck doesn't need to just be an embedded domain specific language for testing ''Haskell'' code. By making instances of Arbitrary for FFI types you can use Haskell and QuickCheck to check code in other languages.<br />
<br />
[[Category:Tutorials]]</div>PhilipNeustromhttps://wiki.haskell.org/index.php?title=Xmonad/Guided_tour_of_the_xmonad_source&diff=20290Xmonad/Guided tour of the xmonad source2008-03-27T03:44:16Z<p>PhilipNeustrom: spelling</p>
<hr />
<div>== Introduction ==<br />
<br />
Do you know a little Haskell and want to see how it can profitably be<br />
applied in a real-world situation? Would you like to quickly get up<br />
to speed on the xmonad source code so you can contribute modules and<br />
patches? Do you aspire to be as cool of a hacker as the xmonad<br />
authors? If so, this might be for you. Specifically, this document<br />
aims to:<br />
<br />
* Provide a readable overview of the xmonad source code for Haskell non-experts interested in contributing extensions or modifications to xmonad, or who are just curious.<br />
<br />
* Highlight some of the uniquenesses of xmonad and the things that make functional languages in general, and Haskell in particular, so ideally suited to this domain.<br />
<br />
This is not a Haskell tutorial. I assume that you already know some<br />
basic Haskell: defining functions and data; the type system; standard<br />
functions, types, and type classes from the Standard Prelude; and at least<br />
a basic familiarity with monads. With that said, however, I do take<br />
frequent detours to highlight and explain more advanced topics and<br />
features of Haskell as they arise.<br />
<br />
==First things first==<br />
<br />
You'll want to have your own version of the xmonad source code to refer to as you read through the guided tour. In particular, you'll want the latest<br />
[http://darcs.net/ darcs] version, which you can easily download by issuing the command:<br />
<br />
darcs get http://code.haskell.org/xmonad<br />
<br />
I intend for this guided tour to keep abreast of the latest darcs changes; if you see something which is out of sync, report it on the xmonad mailing list, or -- even better -- fix it!<br />
<br />
You may also want to refer to the [http://www.haskell.org/haddock/ Haddock]-generated documentation (it's all in the source code, of course, but may be nicer to read this way). You can build the documentation by going into the root of the xmonad source directory, and issuing the command:<br />
<br />
runhaskell Setup haddock<br />
<br />
which will generate HTML documentation in dist/doc/html/xmonad/.<br />
<br />
Without further ado, let's begin!<br />
<br />
== StackSet.hs ==<br />
<br />
StackSet.hs is the pure, functional heart of xmonad. Far removed from corrupting pollutants such as the IO monad and the X server, it is a beautiful, limpid pool of pure code which defines most of the basic data structures used to store the state of xmonad. It is heavily validated by [http://www.cs.chalmers.se/~rjmh/QuickCheck/ QuickCheck] tests; the combination of good use of types and QuickCheck validation means that we can be very confident of the correctness of the code in StackSet.hs.<br />
<br />
[[/StackSet.hs|Continue reading about StackSet.hs...]]<br />
<br />
== Core.hs ==<br />
<br />
The next source file to examine is Core.hs. It defines several core data types and some of the core functionality of xmonad. If StackSet.hs is the heart of xmonad, Core.hs is its guts.<br />
<br />
[[/Core.hs|Continue reading about Core.hs...]]</div>PhilipNeustromhttps://wiki.haskell.org/index.php?title=99_questions/11_to_20&diff=1525799 questions/11 to 202007-08-25T03:45:14Z<p>PhilipNeustrom: lib drop != drop defined, so changed name.</p>
<hr />
<div>__NOTOC__<br />
<br />
This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ Ninety-Nine Prolog Problems] and [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety-Nine Lisp Problems].<br />
<br />
== Problem 11 ==<br />
<br />
(*) Modified run-length encoding. <br />
Modify the result of problem 10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.<br />
<br />
<pre><br />
Example:<br />
* (encode-modified '(a a a a b c c a a d e e e e))<br />
((4 A) B (2 C) (2 A) D (4 E))<br />
<br />
Example in Haskell:<br />
P11> encodeModified "aaaabccaadeeee"<br />
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
data ListItem a = Single a | Multiple Int a<br />
deriving (Show)<br />
<br />
encodeModified :: Eq a => [a] -> [ListItem a]<br />
encodeModified = map encodeHelper . encode<br />
where<br />
encodeHelper (1,x) = Single x<br />
encodeHelper (n,x) = Multiple n x<br />
</haskell><br />
<br />
Again, like in problem 7, we need a utility type because lists in haskell are homogeneous. Afterwards we use the <hask>encode</hask> function from problem 10 and map single instances of a list item to <hask>Single</hask> and multiple ones to <hask>Multiple</hask>.<br />
<br />
The ListItem definition contains 'deriving (Show)' so that we can get interactive output.<br />
<br />
== Problem 12 ==<br />
<br />
(**) Decode a run-length encoded list. <br />
Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.<br />
<br />
<pre><br />
Example in Haskell:<br />
P12> decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
"aaaabccaadeeee"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
decodeModified :: [ListItem a] -> [a]<br />
decodeModified = concatMap decodeHelper<br />
where<br />
decodeHelper (Single x) = [x]<br />
decodeHelper (Multiple n x) = replicate n x<br />
</haskell><br />
<br />
We only need to map single instances of an element to a list containing only one element and multiple ones to a list containing the specified number of elements and concatenate these lists.<br />
<br />
== Problem 13 ==<br />
<br />
(**) Run-length encoding of a list (direct solution). <br />
Implement the so-called run-length encoding data compression method directly. I.e. don't explicitly create the sublists containing the duplicates, as in problem 9, but only count them. As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X.<br />
<br />
<pre><br />
Example:<br />
* (encode-direct '(a a a a b c c a a d e e e e))<br />
((4 A) B (2 C) (2 A) D (4 E))<br />
<br />
Example in Haskell:<br />
P13> encodeDirect "aaaabccaadeeee"<br />
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
encode' :: Eq a => [a] -> [(Int,a)]<br />
encode' = foldr helper []<br />
where<br />
helper x [] = [(1,x)]<br />
helper x (y:ys)<br />
| x == snd y = (1+fst y,x):ys<br />
| otherwise = (1,x):y:ys<br />
<br />
encodeDirect :: Eq a => [a] -> [ListItem a]<br />
encodeDirect = map encodeHelper . encode'<br />
where<br />
encodeHelper (1,x) = Single x<br />
encodeHelper (n,x) = Multiple n x<br />
</haskell><br />
<br />
First of all we could rewrite the function <hask>encode</hask> from problem 10 in a way that is does not create the sublists. Thus, I decided to traverse the original list from right to left (using <hask>foldr</hask>) and to prepend each element to the resulting list in the proper way. Thereafter we only need to modify the function <hask>encodeModified</hask> from problem 11 to use <hask>encode'</hask>.<br />
<br />
== Problem 14 ==<br />
<br />
(*) Duplicate the elements of a list.<br />
<br />
<pre><br />
Example:<br />
* (dupli '(a b c c d))<br />
(A A B B C C C C D D)<br />
<br />
Example in Haskell:<br />
> dupli [1, 2, 3]<br />
[1,1,2,2,3,3]<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
dupli [] = []<br />
dupli (x:xs) = x:x:dupli xs<br />
</haskell><br />
<br />
or, using list comprehension syntax:<br />
<br />
<haskell><br />
dupli list = concat [[x,x] | x <- list]<br />
</haskell><br />
<br />
or, using the list monad:<br />
<haskell><br />
dupli xs = xs >>= (\x -> [x,x])<br />
</haskell><br />
<br />
== Problem 15 ==<br />
<br />
(**) Replicate the elements of a list a given number of times.<br />
<br />
<pre><br />
Example:<br />
* (repli '(a b c) 3)<br />
(A A A B B B C C C)<br />
<br />
Example in Haskell:<br />
> repli "abc" 3<br />
"aaabbbccc"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
repli :: [a] -> Int -> [a]<br />
repli xs n = concatMap (replicate n) xs<br />
</haskell><br />
<br />
== Problem 16 ==<br />
(**) Drop every N'th element from a list.<br />
<br />
<pre><br />
Example:<br />
* (drop '(a b c d e f g h i k) 3)<br />
(A B D E G H K)<br />
<br />
Example in Haskell:<br />
*Main> dropEvery "abcdefghik" 3<br />
"abdeghk"<br />
</pre><br />
<br />
An iterative solution:<br />
<haskell><br />
dropEvery :: [a] -> Int -> [a]<br />
dropEvery [] _ = []<br />
dropEvery (x:xs) n = dropEvery' (x:xs) n 1 where<br />
dropEvery' (x:xs) n i = (if (n `divides` i) then<br />
[] else<br />
[x])<br />
++ (dropEvery' xs n (i+1))<br />
dropEvery' [] _ _ = []<br />
divides x y = y `mod` x == 0<br />
</haskell><br />
<br />
or using zip:<br />
<haskell><br />
dropEvery n = map snd . filter ((n/=) . fst) . zip (cycle [1..n])<br />
</haskell><br />
<br />
== Problem 17 ==<br />
<br />
(*) Split a list into two parts; the length of the first part is given.<br />
<br />
Do not use any predefined predicates.<br />
<br />
<pre><br />
Example:<br />
* (split '(a b c d e f g h i k) 3)<br />
( (A B C) (D E F G H I K))<br />
<br />
Example in Haskell:<br />
*Main> split "abcdefghik" 3<br />
("abc", "defghik")<br />
</pre><br />
<br />
Solution using take and drop:<br />
<haskell><br />
split xs n = (take n xs, drop n xs)<br />
</haskell><br />
Note that this function, with the parameters in the other order, exists as <hask>splitAt</hask>.<br />
<br />
<br />
== Problem 18 ==<br />
<br />
(**) Extract a slice from a list.<br />
<br />
Given two indices, i and k, the slice is the list containing the elements between the i'th and i'th element of the original list (both limits included). Start counting the elements with 1.<br />
<br />
<pre><br />
Example:<br />
* (slice '(a b c d e f g h i k) 3 7)<br />
(C D E F G)<br />
<br />
Example in Haskell:<br />
*Main> slice ['a','b','c','d','e','f','g','h','i','k'] 3 7<br />
"cdefg"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
slice xs (i+1) k = take (k-i) $ drop i xs<br />
</haskell><br />
<br />
== Problem 19 ==<br />
<br />
(**) Rotate a list N places to the left.<br />
<br />
Hint: Use the predefined functions length and (++).<br />
<br />
<pre><br />
Examples:<br />
* (rotate '(a b c d e f g h) 3)<br />
(D E F G H A B C)<br />
<br />
* (rotate '(a b c d e f g h) -2)<br />
(G H A B C D E F)<br />
<br />
Examples in Haskell:<br />
*Main> rotate ['a','b','c','d','e','f','g','h'] 3<br />
"defghabc"<br />
<br />
*Main> rotate ['a','b','c','d','e','f','g','h'] (-2)<br />
"ghabcdef"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
rotate [] _ = []<br />
rotate l 0 = l<br />
rotate (x:xs) (n+1) = rotate (xs ++ [x]) n<br />
rotate l n = rotate l (length l + n)<br />
</haskell><br />
<br />
There are two separate cases:<br />
* If n > 0, move the first element to the end of the list n times.<br />
* If n < 0, convert the problem to the equivalent problem for n > 0 by adding the list's length to n.<br />
<br />
or using cycle:<br />
<haskell><br />
rotate xs n = take len . drop (n `mod` len) . cycle $ xs<br />
where len = length xs<br />
</haskell><br />
<br />
or<br />
<br />
<haskell><br />
rotate xs n = if n >= 0 then<br />
drop n xs ++ take n xs<br />
else let l = ((length xs) + n) in<br />
drop l xs ++ take l xs<br />
</haskell><br />
<br />
== Problem 20 ==<br />
<br />
(*) Remove the K'th element from a list.<br />
<br />
Example in Prolog:<br />
<pre><br />
?- remove_at(X,[a,b,c,d],2,R).<br />
X = b<br />
R = [a,c,d]<br />
</pre><br />
<br />
Example in Lisp:<br />
<pre><br />
* (remove-at '(a b c d) 2)<br />
(A C D)<br />
</pre><br />
(Note that this only returns the residue list, while the Prolog version also returns the deleted element.)<br />
<br />
Example in Haskell:<br />
<pre><br />
*Main> removeAt 1 "abcd"<br />
('b',"acd")<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
removeAt :: Int -> [a] -> (a, [a])<br />
removeAt k xs = case back of<br />
[] -> error "removeAt: index too large"<br />
x:rest -> (x, front ++ rest)<br />
where (front, back) = splitAt k xs<br />
</haskell><br />
<br />
Simply use the <hask>splitAt</hask> to split after k elements.<br />
If the original list has fewer than k+1 elements, the second list will be empty, and there will be no element to extract.<br />
Note that the Prolog and Lisp versions treat 1 as the first element in the list, and the Lisp version appends NIL elements to the end of the list if k is greater than the list length.<br />
<br />
or <br />
<br />
<haskell><br />
removeAt n xs = (xs!!n,take n xs ++ drop (n+1) xs)<br />
</haskell><br />
<br />
[[Category:Tutorials]]</div>PhilipNeustromhttps://wiki.haskell.org/index.php?title=99_questions/11_to_20&diff=1525699 questions/11 to 202007-08-25T03:18:07Z<p>PhilipNeustrom: solution given didn't work, mine works</p>
<hr />
<div>__NOTOC__<br />
<br />
This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ Ninety-Nine Prolog Problems] and [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety-Nine Lisp Problems].<br />
<br />
== Problem 11 ==<br />
<br />
(*) Modified run-length encoding. <br />
Modify the result of problem 10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.<br />
<br />
<pre><br />
Example:<br />
* (encode-modified '(a a a a b c c a a d e e e e))<br />
((4 A) B (2 C) (2 A) D (4 E))<br />
<br />
Example in Haskell:<br />
P11> encodeModified "aaaabccaadeeee"<br />
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
data ListItem a = Single a | Multiple Int a<br />
deriving (Show)<br />
<br />
encodeModified :: Eq a => [a] -> [ListItem a]<br />
encodeModified = map encodeHelper . encode<br />
where<br />
encodeHelper (1,x) = Single x<br />
encodeHelper (n,x) = Multiple n x<br />
</haskell><br />
<br />
Again, like in problem 7, we need a utility type because lists in haskell are homogeneous. Afterwards we use the <hask>encode</hask> function from problem 10 and map single instances of a list item to <hask>Single</hask> and multiple ones to <hask>Multiple</hask>.<br />
<br />
The ListItem definition contains 'deriving (Show)' so that we can get interactive output.<br />
<br />
== Problem 12 ==<br />
<br />
(**) Decode a run-length encoded list. <br />
Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.<br />
<br />
<pre><br />
Example in Haskell:<br />
P12> decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
"aaaabccaadeeee"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
decodeModified :: [ListItem a] -> [a]<br />
decodeModified = concatMap decodeHelper<br />
where<br />
decodeHelper (Single x) = [x]<br />
decodeHelper (Multiple n x) = replicate n x<br />
</haskell><br />
<br />
We only need to map single instances of an element to a list containing only one element and multiple ones to a list containing the specified number of elements and concatenate these lists.<br />
<br />
== Problem 13 ==<br />
<br />
(**) Run-length encoding of a list (direct solution). <br />
Implement the so-called run-length encoding data compression method directly. I.e. don't explicitly create the sublists containing the duplicates, as in problem 9, but only count them. As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X.<br />
<br />
<pre><br />
Example:<br />
* (encode-direct '(a a a a b c c a a d e e e e))<br />
((4 A) B (2 C) (2 A) D (4 E))<br />
<br />
Example in Haskell:<br />
P13> encodeDirect "aaaabccaadeeee"<br />
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
encode' :: Eq a => [a] -> [(Int,a)]<br />
encode' = foldr helper []<br />
where<br />
helper x [] = [(1,x)]<br />
helper x (y:ys)<br />
| x == snd y = (1+fst y,x):ys<br />
| otherwise = (1,x):y:ys<br />
<br />
encodeDirect :: Eq a => [a] -> [ListItem a]<br />
encodeDirect = map encodeHelper . encode'<br />
where<br />
encodeHelper (1,x) = Single x<br />
encodeHelper (n,x) = Multiple n x<br />
</haskell><br />
<br />
First of all we could rewrite the function <hask>encode</hask> from problem 10 in a way that is does not create the sublists. Thus, I decided to traverse the original list from right to left (using <hask>foldr</hask>) and to prepend each element to the resulting list in the proper way. Thereafter we only need to modify the function <hask>encodeModified</hask> from problem 11 to use <hask>encode'</hask>.<br />
<br />
== Problem 14 ==<br />
<br />
(*) Duplicate the elements of a list.<br />
<br />
<pre><br />
Example:<br />
* (dupli '(a b c c d))<br />
(A A B B C C C C D D)<br />
<br />
Example in Haskell:<br />
> dupli [1, 2, 3]<br />
[1,1,2,2,3,3]<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
dupli [] = []<br />
dupli (x:xs) = x:x:dupli xs<br />
</haskell><br />
<br />
or, using list comprehension syntax:<br />
<br />
<haskell><br />
dupli list = concat [[x,x] | x <- list]<br />
</haskell><br />
<br />
or, using the list monad:<br />
<haskell><br />
dupli xs = xs >>= (\x -> [x,x])<br />
</haskell><br />
<br />
== Problem 15 ==<br />
<br />
(**) Replicate the elements of a list a given number of times.<br />
<br />
<pre><br />
Example:<br />
* (repli '(a b c) 3)<br />
(A A A B B B C C C)<br />
<br />
Example in Haskell:<br />
> repli "abc" 3<br />
"aaabbbccc"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
repli :: [a] -> Int -> [a]<br />
repli xs n = concatMap (replicate n) xs<br />
</haskell><br />
<br />
== Problem 16 ==<br />
(**) Drop every N'th element from a list.<br />
<br />
<pre><br />
Example:<br />
* (drop '(a b c d e f g h i k) 3)<br />
(A B D E G H K)<br />
<br />
Example in Haskell:<br />
*Main> drop' "abcdefghik" 3<br />
"abdeghk"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
drop' [] _ = []<br />
drop' l n = (take (n-1) l) ++ reverse (take (length l - n) (reverse l))<br />
</haskell><br />
<br />
Note that drop is one of the standard Haskell functions, so redefining it is generally not a good idea; we define drop' (drop prime) instead.<br />
<br />
or using zip:<br />
<haskell><br />
drop n = map snd . filter ((n/=) . fst) . zip (cycle [1..n])<br />
</haskell><br />
<br />
== Problem 17 ==<br />
<br />
(*) Split a list into two parts; the length of the first part is given.<br />
<br />
Do not use any predefined predicates.<br />
<br />
<pre><br />
Example:<br />
* (split '(a b c d e f g h i k) 3)<br />
( (A B C) (D E F G H I K))<br />
<br />
Example in Haskell:<br />
*Main> split "abcdefghik" 3<br />
("abc", "defghik")<br />
</pre><br />
<br />
Solution using take and drop:<br />
<haskell><br />
split xs n = (take n xs, drop n xs)<br />
</haskell><br />
Note that this function, with the parameters in the other order, exists as <hask>splitAt</hask>.<br />
<br />
<br />
== Problem 18 ==<br />
<br />
(**) Extract a slice from a list.<br />
<br />
Given two indices, i and k, the slice is the list containing the elements between the i'th and i'th element of the original list (both limits included). Start counting the elements with 1.<br />
<br />
<pre><br />
Example:<br />
* (slice '(a b c d e f g h i k) 3 7)<br />
(C D E F G)<br />
<br />
Example in Haskell:<br />
*Main> slice ['a','b','c','d','e','f','g','h','i','k'] 3 7<br />
"cdefg"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
slice xs (i+1) k = take (k-i) $ drop i xs<br />
</haskell><br />
<br />
== Problem 19 ==<br />
<br />
(**) Rotate a list N places to the left.<br />
<br />
Hint: Use the predefined functions length and (++).<br />
<br />
<pre><br />
Examples:<br />
* (rotate '(a b c d e f g h) 3)<br />
(D E F G H A B C)<br />
<br />
* (rotate '(a b c d e f g h) -2)<br />
(G H A B C D E F)<br />
<br />
Examples in Haskell:<br />
*Main> rotate ['a','b','c','d','e','f','g','h'] 3<br />
"defghabc"<br />
<br />
*Main> rotate ['a','b','c','d','e','f','g','h'] (-2)<br />
"ghabcdef"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
rotate [] _ = []<br />
rotate l 0 = l<br />
rotate (x:xs) (n+1) = rotate (xs ++ [x]) n<br />
rotate l n = rotate l (length l + n)<br />
</haskell><br />
<br />
There are two separate cases:<br />
* If n > 0, move the first element to the end of the list n times.<br />
* If n < 0, convert the problem to the equivalent problem for n > 0 by adding the list's length to n.<br />
<br />
or using cycle:<br />
<haskell><br />
rotate xs n = take len . drop (n `mod` len) . cycle $ xs<br />
where len = length xs<br />
</haskell><br />
<br />
or<br />
<br />
<haskell><br />
rotate xs n = if n >= 0 then<br />
drop n xs ++ take n xs<br />
else let l = ((length xs) + n) in<br />
drop l xs ++ take l xs<br />
</haskell><br />
<br />
== Problem 20 ==<br />
<br />
(*) Remove the K'th element from a list.<br />
<br />
Example in Prolog:<br />
<pre><br />
?- remove_at(X,[a,b,c,d],2,R).<br />
X = b<br />
R = [a,c,d]<br />
</pre><br />
<br />
Example in Lisp:<br />
<pre><br />
* (remove-at '(a b c d) 2)<br />
(A C D)<br />
</pre><br />
(Note that this only returns the residue list, while the Prolog version also returns the deleted element.)<br />
<br />
Example in Haskell:<br />
<pre><br />
*Main> removeAt 1 "abcd"<br />
('b',"acd")<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
removeAt :: Int -> [a] -> (a, [a])<br />
removeAt k xs = case back of<br />
[] -> error "removeAt: index too large"<br />
x:rest -> (x, front ++ rest)<br />
where (front, back) = splitAt k xs<br />
</haskell><br />
<br />
Simply use the <hask>splitAt</hask> to split after k elements.<br />
If the original list has fewer than k+1 elements, the second list will be empty, and there will be no element to extract.<br />
Note that the Prolog and Lisp versions treat 1 as the first element in the list, and the Lisp version appends NIL elements to the end of the list if k is greater than the list length.<br />
<br />
or <br />
<br />
<haskell><br />
removeAt n xs = (xs!!n,take n xs ++ drop (n+1) xs)<br />
</haskell><br />
<br />
[[Category:Tutorials]]</div>PhilipNeustromhttps://wiki.haskell.org/index.php?title=99_questions/11_to_20&diff=1525599 questions/11 to 202007-08-25T02:52:00Z<p>PhilipNeustrom: i believe this is correct and the former incorrect</p>
<hr />
<div>__NOTOC__<br />
<br />
This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ Ninety-Nine Prolog Problems] and [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety-Nine Lisp Problems].<br />
<br />
== Problem 11 ==<br />
<br />
(*) Modified run-length encoding. <br />
Modify the result of problem 10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.<br />
<br />
<pre><br />
Example:<br />
* (encode-modified '(a a a a b c c a a d e e e e))<br />
((4 A) B (2 C) (2 A) D (4 E))<br />
<br />
Example in Haskell:<br />
P11> encodeModified "aaaabccaadeeee"<br />
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
data ListItem a = Single a | Multiple Int a<br />
deriving (Show)<br />
<br />
encodeModified :: Eq a => [a] -> [ListItem a]<br />
encodeModified = map encodeHelper . encode<br />
where<br />
encodeHelper (1,x) = Single x<br />
encodeHelper (n,x) = Multiple n x<br />
</haskell><br />
<br />
Again, like in problem 7, we need a utility type because lists in haskell are homogeneous. Afterwards we use the <hask>encode</hask> function from problem 10 and map single instances of a list item to <hask>Single</hask> and multiple ones to <hask>Multiple</hask>.<br />
<br />
The ListItem definition contains 'deriving (Show)' so that we can get interactive output.<br />
<br />
== Problem 12 ==<br />
<br />
(**) Decode a run-length encoded list. <br />
Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.<br />
<br />
<pre><br />
Example in Haskell:<br />
P12> decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
"aaaabccaadeeee"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
decodeModified :: [ListItem a] -> [a]<br />
decodeModified = concatMap decodeHelper<br />
where<br />
decodeHelper (Single x) = [x]<br />
decodeHelper (Multiple n x) = replicate n x<br />
</haskell><br />
<br />
We only need to map single instances of an element to a list containing only one element and multiple ones to a list containing the specified number of elements and concatenate these lists.<br />
<br />
== Problem 13 ==<br />
<br />
(**) Run-length encoding of a list (direct solution). <br />
Implement the so-called run-length encoding data compression method directly. I.e. don't explicitly create the sublists containing the duplicates, as in problem 9, but only count them. As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X.<br />
<br />
<pre><br />
Example:<br />
* (encode-direct '(a a a a b c c a a d e e e e))<br />
((4 A) B (2 C) (2 A) D (4 E))<br />
<br />
Example in Haskell:<br />
P13> encodeDirect "aaaabccaadeeee"<br />
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
encode' :: Eq a => [a] -> [(Int,a)]<br />
encode' = foldr helper []<br />
where<br />
helper x [] = [(1,x)]<br />
helper x (y:ys)<br />
| x == snd y = (1+fst y,x):ys<br />
| otherwise = (1,x):y:ys<br />
<br />
encodeDirect :: Eq a => [a] -> [ListItem a]<br />
encodeDirect = map encodeHelper . encode'<br />
where<br />
encodeHelper (1,x) = Single x<br />
encodeHelper (n,x) = Multiple n x<br />
</haskell><br />
<br />
First of all we could rewrite the function <hask>encode</hask> from problem 10 in a way that is does not create the sublists. Thus, I decided to traverse the original list from right to left (using <hask>foldr</hask>) and to prepend each element to the resulting list in the proper way. Thereafter we only need to modify the function <hask>encodeModified</hask> from problem 11 to use <hask>encode'</hask>.<br />
<br />
== Problem 14 ==<br />
<br />
(*) Duplicate the elements of a list.<br />
<br />
<pre><br />
Example:<br />
* (dupli '(a b c c d))<br />
(A A B B C C C C D D)<br />
<br />
Example in Haskell:<br />
> dupli [1, 2, 3]<br />
[1,1,2,2,3,3]<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
dupli [] = []<br />
dupli (x:xs) = x:x:dupli xs<br />
</haskell><br />
<br />
or, using list comprehension syntax:<br />
<br />
<haskell><br />
dupli list = concat [[x,x] | x <- list]<br />
</haskell><br />
<br />
or, using the list monad:<br />
<haskell><br />
dupli xs = xs >>= (\x -> [x,x])<br />
</haskell><br />
<br />
== Problem 15 ==<br />
<br />
(**) Replicate the elements of a list a given number of times.<br />
<br />
<pre><br />
Example:<br />
* (repli '(a b c) 3)<br />
(A A A B B B C C C)<br />
<br />
Example in Haskell:<br />
> repli "abc" 3<br />
"aaabbbccc"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
repli :: [a] -> Int -> [a]<br />
repli xs n = concatMap (replicate n) xs<br />
</haskell><br />
<br />
== Problem 16 ==<br />
(**) Drop every N'th element from a list.<br />
<br />
<pre><br />
Example:<br />
* (drop '(a b c d e f g h i k) 3)<br />
(A B D E G H K)<br />
<br />
Example in Haskell:<br />
*Main> drop' "abcdefghik" 3<br />
"abdeghk"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
drop' [] _ = []<br />
drop' xs n = (take (n-1) xs) ++ (drop' (drop n xs) n)<br />
</haskell><br />
<br />
Note that drop is one of the standard Haskell functions, so redefining it is generally not a good idea; we define drop' (drop prime) instead.<br />
<br />
or using zip:<br />
<haskell><br />
drop n = map snd . filter ((n/=) . fst) . zip (cycle [1..n])<br />
</haskell><br />
<br />
== Problem 17 ==<br />
<br />
(*) Split a list into two parts; the length of the first part is given.<br />
<br />
Do not use any predefined predicates.<br />
<br />
<pre><br />
Example:<br />
* (split '(a b c d e f g h i k) 3)<br />
( (A B C) (D E F G H I K))<br />
<br />
Example in Haskell:<br />
*Main> split "abcdefghik" 3<br />
("abc", "defghik")<br />
</pre><br />
<br />
Solution using take and drop:<br />
<haskell><br />
split xs n = (take n xs, drop n xs)<br />
</haskell><br />
Note that this function, with the parameters in the other order, exists as <hask>splitAt</hask>.<br />
<br />
<br />
== Problem 18 ==<br />
<br />
(**) Extract a slice from a list.<br />
<br />
Given two indices, i and k, the slice is the list containing the elements between the i'th and i'th element of the original list (both limits included). Start counting the elements with 1.<br />
<br />
<pre><br />
Example:<br />
* (slice '(a b c d e f g h i k) 3 7)<br />
(C D E F G)<br />
<br />
Example in Haskell:<br />
*Main> slice ['a','b','c','d','e','f','g','h','i','k'] 3 7<br />
"cdefg"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
slice xs (i+1) k = take (k-i) $ drop i xs<br />
</haskell><br />
<br />
== Problem 19 ==<br />
<br />
(**) Rotate a list N places to the left.<br />
<br />
Hint: Use the predefined functions length and (++).<br />
<br />
<pre><br />
Examples:<br />
* (rotate '(a b c d e f g h) 3)<br />
(D E F G H A B C)<br />
<br />
* (rotate '(a b c d e f g h) -2)<br />
(G H A B C D E F)<br />
<br />
Examples in Haskell:<br />
*Main> rotate ['a','b','c','d','e','f','g','h'] 3<br />
"defghabc"<br />
<br />
*Main> rotate ['a','b','c','d','e','f','g','h'] (-2)<br />
"ghabcdef"<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
rotate [] _ = []<br />
rotate l 0 = l<br />
rotate (x:xs) (n+1) = rotate (xs ++ [x]) n<br />
rotate l n = rotate l (length l + n)<br />
</haskell><br />
<br />
There are two separate cases:<br />
* If n > 0, move the first element to the end of the list n times.<br />
* If n < 0, convert the problem to the equivalent problem for n > 0 by adding the list's length to n.<br />
<br />
or using cycle:<br />
<haskell><br />
rotate xs n = take len . drop (n `mod` len) . cycle $ xs<br />
where len = length xs<br />
</haskell><br />
<br />
or<br />
<br />
<haskell><br />
rotate xs n = if n >= 0 then<br />
drop n xs ++ take n xs<br />
else let l = ((length xs) + n) in<br />
drop l xs ++ take l xs<br />
</haskell><br />
<br />
== Problem 20 ==<br />
<br />
(*) Remove the K'th element from a list.<br />
<br />
Example in Prolog:<br />
<pre><br />
?- remove_at(X,[a,b,c,d],2,R).<br />
X = b<br />
R = [a,c,d]<br />
</pre><br />
<br />
Example in Lisp:<br />
<pre><br />
* (remove-at '(a b c d) 2)<br />
(A C D)<br />
</pre><br />
(Note that this only returns the residue list, while the Prolog version also returns the deleted element.)<br />
<br />
Example in Haskell:<br />
<pre><br />
*Main> removeAt 1 "abcd"<br />
('b',"acd")<br />
</pre><br />
<br />
Solution:<br />
<haskell><br />
removeAt :: Int -> [a] -> (a, [a])<br />
removeAt k xs = case back of<br />
[] -> error "removeAt: index too large"<br />
x:rest -> (x, front ++ rest)<br />
where (front, back) = splitAt k xs<br />
</haskell><br />
<br />
Simply use the <hask>splitAt</hask> to split after k elements.<br />
If the original list has fewer than k+1 elements, the second list will be empty, and there will be no element to extract.<br />
Note that the Prolog and Lisp versions treat 1 as the first element in the list, and the Lisp version appends NIL elements to the end of the list if k is greater than the list length.<br />
<br />
or <br />
<br />
<haskell><br />
removeAt n xs = (xs!!n,take n xs ++ drop (n+1) xs)<br />
</haskell><br />
<br />
[[Category:Tutorials]]</div>PhilipNeustrom