Re: [Haskell-cafe] Hints for Euler Problem 11
I came up with this function to try to extract the main diagonal. getDiag :: [[a]] - [a] getDiag = map (head . head) . iterate (tail . map tail) The problem is, this function doesn't work unless I have an infinite grid. Could anyone provide me with some hints to lead me in the right direction? I think Dan's hint is pretty good, but a hint for this *specific* part of the problem, rather than the whole thing. 'head' and 'tail' blow up on empty lists. So any kind of solution involving iterate and similar with them tends to eventually blow up on finite lists. (take 1) and (drop 1) are rather similar functions, but they simply give [] on [] instead of blowing up. Then, on a finite list, you just keep getting []s after a while, which you can trim with takeWhile (not . null). Another approach is to replace iterate with an unfoldr; an unfoldr is rather like a 'general iterate' which 'knows when to stop' : it stops when your unfolding function gives Nothing. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hints for Euler Problem 11
On Thu, Jul 19, 2007 at 11:39:26PM -0400, Ronald Guida wrote: In Problem 11, a 20x20 grid of numbers is given, and the problem is to find the largest product of four numbers along a straight line in the grid. The line can be horizontal, vertical, or diagonal. I found it easier to work with Arrays in this example: grid :: [[Integer]] grid = readGrid gridText gridArr :: [[Integer]] - Array (Int, Int) Integer gridArr = array ((0, 0), (19, 19)) Then you can define a handy function for extracting whatever combination of indices you need: extractBy :: (Ix i, Ord a) = ((i, e) - a) - Array i e - [[e]] extractBy f = map (map snd) . groupBy (equals f) . sortBy (comparing f) . assocs And from there on you can work your way out of this problem by replacing ??? with functions that map ((i, j), v) to some value common for same row, col, or diagonal: rows = extractBy ??? cols = extractBy ??? diags = extractBy ??? adiags = extractBy ??? makeGroups :: Int - [a] - [[a]] makeGroups 0 _ = [] makeGroups n xs = let ys = take n xs in if n == length ys then ys : (makeGroups n $ tail xs) else [] The above can be shortened to: makeGroupsOf n = map (take n) . tails From here on you should be able to compute products of whatever is required. Good luck and have fun! Regards, -- Krzysztof Kościuszkiewicz Skype: dr.vee, Gadu: 111851, Jabber: [EMAIL PROTECTED] Phone IRL: +353851383329, Phone PL: +48783303040 Simplicity is the ultimate sophistication -- Leonardo da Vinci ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] List minimum - performance question
Hello all, Inspired by exercise on the minimal value of a given list I tried myself produce several versions of such a function: exercise: using just ($), head, filter, null, id, map, () without explicit recursion definition direct-forward: direct implementation using forward recursion, if-then-else, () direct-backward: direct implementation using backward recursion, if-then-else, () foldl: using foldl, lambda abstraction, if-then-else, () foldr: using foldr, lambda abstraction, if-then-else, () From a recursion point of view, I see a similarity between direct-forward and foldl. Of course, the same similarity is between direct-backward and foldr. Am I right? If yes, then there is something strange in the results I have gained (see below). I did my measurements in winhugs (Version: Sep 2006) for lists of length 10, 100, 1000 and 50 elements. I tested on list with the same constant, list where the first number is minimal (these two cases are from this point of view similar/the same), lists, where some element in the middle is minimal, and finally lists, where the last element is the minimal one. As for constant and first minimal element list I got the same result, we can join them and have just three categories of lists, let's call them first, mid, last. Even if I know that using number of reductions and number of cells does not provide exact results, I assume that impact of parameter and printing of the result is the same for all tested functions and is either constant for the result printing (always number 1 in the result) and at most linear in the parameter processing (I would assume no direct impact here, just algorithm influence, is that right?). Thus, the results may be compared. First of all, the time/reduction complexity (n is a length of the list): first midlast exercise 9n+34not evaluated4.5n^2+21.5n+17 direct-forward 7n+157n+15 7n+15 direct-backward 7n+157n+15 7n+15 foldl8n+148n+14 8n+14 foldr8n+148n+14 8n+14 There is nothing special on the results, the exercise solution was not evaluated for the middle element lists as the position of the minimal value in the list is a parameter of the function. Now, let me show results for number of used cells: first midlast exercise 10n+54 not evaluated 5n^2+29n+26 direct-forward 8n+248n+25 9n+23 direct-backward 9n+229n+22 9n+22 foldl11n+22 11n+22 11n+22 foldr10n+23 10n+23 10n+23 Again, roughly looking at the results, there is nothing special, average space complexity is as it may be expected. Looking at the exact formulas, there are two things that come strange to me: 1) From a recursion point of view, there are pairs direct-forward ~ foldl and direct-backward ~ foldr. Nevertheless, from a space consumption point of view, this doesn't hold and the pairs are swapped. Why? Is this a winhugs specialty? Is this due to reduction strategy? Laziness? 2) Direct-forward implementation provides three different formulas. Why? Why the mid formula is fixed no matter where the minimal value is? Thanks for any answers/hints/references. Especially, if this is RTFM one. ;-) Dusan P.S. I know, that sources may be helpful, but as this is an exercise I don't want to provide them directly to the list. ;-) But I can provide them, of course. :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] GHC 6.6.1: Where is Graphics.SOE ?
Olivier Boudry [EMAIL PROTECTED] wrote: (Wed Jul 18 11:56:56 EDT 2007) Hi Dmitri, I built gtk2hs on Windows with GHC 6.6.1 and gtk2hs-0.9.11. Here's are the steps that worked for me: (not sure I didn't missed some) First you need to install a GTK+ development package for windows. I think mine comes from http://gladewin32.sourceforge.net/modules/wfdownloads/ Then you must have MSYS and MinGW installed on your computer. You'll find information on how to install this here: http://hackage.haskell.org/trac/ghc/wiki/Building/Windows. Once you've installed that stuff you can start a MSYS shell. You'll need to set some environment variables for GTK (adapt to your path): export GTK_BASEPATH=/c/GTK_2.0 export GTK_CONFIG_PATH=/c/GTK_2.0/lib/pkgconfig Cd to the gtk2hs source directory and type: ./configure --prefix=/c/Progra~1/Haskell make make install Hope this helps. Good luck, Olivier. Oliver, thanks! I tried that, yet have some problems. I use: GHC 6.6.1, current development version of Gtk2hs (not sure what version), Gtk+ 2.10.11 (Win32) and latest available from MinGW distributions: MSYS-1.0.10.exe msysDTK-1.0.1.exe msys-autoconf-2.59.tar.bz2 msys-automake-1.8.2.tar.bz2 msys-libtool-1.5.tar.bz2 Problem 1. Gtk2hs build requires to run autoreconf. So in MSYS I have: $ autoreconf /usr/share/aclocal/autoopts.m4:22: warning: underquoted definition of AG_PATH_AUTOOPTS run info '(automake)Extending aclocal' or see http://sources.redhat.com/automake/automake.html#Extending%20aclocal configure.ac:101: error: possibly undefined macro: AC_MSG_ERROR If this token and others are legitimate, please use m4_pattern_allow. See the Autoconf documentation. autoreconf: /usr/bin/autoconf failed with exit status: 1 Notwithstanding this error autoreconf creates configure script. When I run it I get: Problem 2. $ ./configure --with-hc=/c/usr/ghc-6.6.1 --prefix=/c/usr/ghc-6.6.1 checking for a BSD-compatible install... /bin/install -c checking whether build environment is sane... yes checking for gawk... gawk checking whether make sets $(MAKE)... yes checking build system type... i686-pc-mingw32 checking host system type... i686-pc-mingw32 checking for style of include used by make... GNU checking for gcc... no checking for cc... no checking for cc... no checking for cl... no configure: error: no acceptable C compiler found in $PATH Questions: 1) Should I ignore autoreconf errors? 2) I thought that building Gtk2hs is done with GHC only. Is it right that build requires C compiler? 3) Any other ideas what is wrong with this build? Thanks! -- Dmitri O. Kondratiev [EMAIL PROTECTED] http://www.geocities.com/dkondr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Minim interpreter
Anyone care to code up a Haskell implementation of this trivial interpreter for comparison: http://groups.google.co.uk/group/comp.lang.lisp/browse_frm/thread/7b1ab36f5d5cce0a/0ca59e0bfb794e07?hl=en#0ca59e0bfb794e07 -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] i need wxHaskell compiled for ghc 6.6.1 on Windows
Hello haskell-cafe, can anyone provide wxHaskell already compiled/compilable with ghc 6.6.1 on Windows? -- Best regards, Bulat mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Hints for Euler Problem 11
Ronald Guida ronguida at mindspring.com writes: I started looking at the Euler problems [1]. I had no trouble with problems 1 through 10, but I'm stuck on problem 11. I am aware that the solutions are available ([2]), but I would rather not look just yet. I am the author of that solution http://www.haskell.org/haskellwiki/Euler_problems/11_to_20 My solution has a word count of 191 words, which might amuse you considering that there are 400 entries to the table. Hint: zipWith4 is your friend; see Data.List. Feed it four lists of different lengths, and it stops gracefully when any list runs out. So one can use skew (w,x,y,z) = (w, drop 1 x, drop 2 y, drop 3 z) to stagger four lists before multiplying corresponding elements. I was using the Euler problems to learn Haskell, as you're doing, so I don't know if my solution is the most readable one. I built up a vocabulary of short functions to compose. I remember finding it odd at the time that I had to use tuples to handle multiple return values. C annoyed me for being mostly peanut shells and few peanuts: one seems to spend all of one's time tossing arguments back and forth onto the stack for nested function calls, when it seemed that the real work could be done in place with less effort. Sure, optimizing compilers do exactly that, with registers, but then why was I explicitly worrying about passing around all of these arguments, in order to code in C? Haskell is much more concise, but the tupling and untupling in my code seems a distraction, even looking back at it now. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Producing MinimumValue
Sebastian Sylvan wrote: minimumValue :: [Int] - Int minimumValue ns = head (iSort ns) If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n). Actually, since Haskell is lazy and only the first element is required for minimumValue, the above algorithm should be O(n). Just for reference: http://thread.gmane.org/gmane.comp.lang.haskell.general/15007 Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Producing MinimumValue
2007/7/19, Jason Dagit [EMAIL PROTECTED]: I prefer, allEqual [] = True allEqual xs = foldl1 (==) xs But, unfortunately, it's not a one liner like yours (unless you allow allEqual [] = undefined). Oh and silly me, that only works for [Bool]. My natural instinct is, allEqual [] = True allEqual (x:xs) = all (== x) xs with the same caveat about allEqual [] as in your case. - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Producing MinimumValue
Hello Benja, Friday, July 20, 2007, 6:10:15 PM, you wrote: My natural instinct is, allEqual [] = True allEqual (x:xs) = all (== x) xs with the same caveat about allEqual [] as in your case. allEqual xs = all (== head xs) xs -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Producing MinimumValue
2007/7/20, Bulat Ziganshin [EMAIL PROTECTED]: allEqual [] = True allEqual (x:xs) = all (== x) xs with the same caveat about allEqual [] as in your case. allEqual xs = all (== head xs) xs Rght. Not evaluated in the edge case, because xs is empty. Didn't think of that, nice :-) - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hints for Euler Problem 11
Ronald Guida wrote: Hi, again. I started looking at the Euler problems [1]. I had no trouble with problems 1 through 10, but I'm stuck on problem 11. I am aware that the solutions are available ([2]), but I would rather not look just yet. [...] FWIW I used a 2D array and a function to retrieve the values in every direction from a given row,col, for each direction valid for that array index. Getting the 4 vals in each direction is done by iterating 2 functions on the (row,col) index to move in the right direction I.e., vals (row,col) = north : south : ... : [] where north = if toohigh then [] else stream (subtract 1) (id) south = if toolow then [] else stream (+1) (id) ... -- View this message in context: http://www.nabble.com/Hints-for-Euler-Problem-11-tf4114963.html#a11710468 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hints for Euler Problem 11
Jim Burton wrote: Ronald Guida wrote: Hi, again. I started looking at the Euler problems [1]. I had no trouble with problems 1 through 10, but I'm stuck on problem 11. I am aware that the solutions are available ([2]), but I would rather not look just yet. [...] FWIW I used a 2D array and a function to retrieve the values in every direction from a given row,col, for each direction valid for that array index. Getting the 4 vals in each direction is done by iterating 2 functions on the (row,col) index to move in the right direction I.e., vals (row,col) = north : south : ... : [] where north = if toohigh then [] else stream (subtract 1) (id) south = if toolow then [] else stream (+1) (id) ... where `stream' is badly named -- rather than a stream it's the 4 vals in that direction. -- View this message in context: http://www.nabble.com/Hints-for-Euler-Problem-11-tf4114963.html#a11710683 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Speedy parsing
2007/7/20, Tillmann Rendel [EMAIL PROTECTED]: Re, Joseph (IT) wrote: At this point I'm out of ideas, so I was hoping someone could identify something stupid I've done (I'm still novice of FP in general, let alone for high performance) or direct me to a guide,website,paper,library, or some other form of help. I think that your problem is simply an excess of lazyness :). foldr is too lazy: you pass huge structures to fold, that you evaluate anyway. Try to import Data.List and use foldl' (not foldl), that is strict. Being left fold, you probably need to rework a bit your functions (I tried to simply flip them, but the result of the program wereflipped too), but the time (and memory) difference is unbelievabl (foldl' is constant in memory allocation). Salvatore ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Hints for Euler Problem 11
Thank you for all the hints.
Here's how I ended up solving it:
module Main
where
import Data.List
import Data.Maybe
gridText = 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n\
\49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n\
\81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n\
\52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n\
\22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n\
\24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n\
\32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n\
\67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n\
\24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n\
\21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n\
\78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n\
\16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n\
\86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n\
\19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n\
\04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n\
\88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n\
\04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n\
\20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n\
\20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n\
\01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
type Grid a = [[a]]
readGrid :: (Read a) = String - Grid a
readGrid = (map ((map read) . words)) . lines
grid :: Grid Integer
grid = readGrid gridText
takeExactly - extract the first n elements of a list;
there must be at least n elements, n 0
takeExactly :: (Monad m) = Int - [a] - m [a]
takeExactly n xs | n 0 =
let ys = take n xs in
if length ys == n
then return ys
else fail takeExactly: list is too short
| otherwise = fail takeExactly: empty list
extractGroups :: Int - [[a]] - [[a]]
extractGroups n = catMaybes . map (takeExactly n)
gridExtractGroups :: Int - Grid [a] - Grid [a]
gridExtractGroups n = filter (not . null) . map (extractGroups n)
gridTails - generate a list of grids with sequential starting places
Parameters a and b determine the offset bewteen successive grids,
as follows: (note that a, b may not be negative)
Grid x_{0,1.., 0,1..} -
[ Grid x_{ 0, 1 .., 0, 1 ..}
, Grid x_{ a, a+1 .., b, b+1 ..}
, Grid x_{2*a, 2*a+1 .., 2*b, 2*b+1 ..}
etc. ]
gridTails :: (Int, Int) - Grid a - [Grid a]
gridTails (a,b) xs =
if not $ null $ concat xs
then xs : gridTails (a,b) ((drop a) $ map (drop b) xs)
else []
transpose3d - converts x_{i,j,k} to x_{j,k,i}
using sequence is x_{i,j,k} - x_{j,i,k} - x_{j,k,i}
transpose3d :: [Grid a] - Grid [a]
transpose3d = map transpose . transpose
reorient - transform a direction vector so that both components are
non-negative
reorient :: (Int, Int) - (Grid a - Grid a, (Int, Int), Grid b - Grid b)
reorient (a,b)
| a=0 b=0 = (id , ( a, b), id)
| a 0 b=0 = (reverse , (-a, b), reverse)
| a=0 b 0 = (map reverse , ( a,-b), map reverse)
| a 0 b 0 = (reverse . map reverse, (-a,-b), reverse . map reverse)
makeEls - convert a grid to grid of Equidistant Letter Sequences
makeEls :: (Int, Int) - Grid a - Grid [a]
makeEls vec = let (reflect2, rvec, reflect1) = reorient vec in
reflect2 . transpose3d . gridTails rvec . reflect1
getGroups :: Int - (Int, Int) - Grid a - [[a]]
getGroups n (a,b) = concat . gridExtractGroups n . makeEls (a,b)
findMaxProduct :: (Ord a, Num a) = Int - (Int, Int) - Grid a - a
findMaxProduct n (a,b) = maximum . map product . getGroups n (a,b)
main :: IO()
main = do
print $ findMaxProduct 4 (1,0) grid
print $ findMaxProduct 4 (0,1) grid
print $ findMaxProduct 4 (1,1) grid
print $ findMaxProduct 4 (1,-1) grid
-- Ron
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Speedy parsing
Ah, I thought I might have to resort to one of the ByteStrings modules. I've heard of them but was more or less avoiding them due to some complexities with installing extra libraries in my current dev environment. I'll try to work that out with the sysadmins and try it out. Thanks for the advice -Original Message- From: Tillmann Rendel [mailto:[EMAIL PROTECTED] Sent: Thursday, July 19, 2007 8:48 PM To: Re, Joseph (IT) Cc: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Speedy parsing Re, Joseph (IT) wrote: At this point I'm out of ideas, so I was hoping someone could identify something stupid I've done (I'm still novice of FP in general, let alone for high performance) or direct me to a guide,website,paper,library, or some other form of help. Two ideas about your aproaches: (1) try to avoid explicit recursion by using some standard library functions instead. it's easier (once you learned the library) and may be faster (since the library may be written in a easy to optimize style). (2) try lazy ByteStrings, they should be faster. http://www.cse.unsw.edu.au/~dons/fps.html As an example, sorting of the individual lines of a csv files by key. csv parses the csv format, uncsv produces it. these functions can't handle '=' in the key or ',' in the key or value. treesort sorts by inserting stuff into a map and removing it in ascending order: import System.Environment import qualified Data.ByteString.Lazy.Char8 as B import qualified Data.Map as Map import Control.Arrow (second) csv = (map $ map $ second B.tail . B.break (== '=')) . (map $ B.split ',') . (B.split '\n') uncsv = (B.join $ B.pack \n) . (map $ B.join $ B.pack ,) . (map $ map $ \(key, val) - B.concat [key, B.pack =, val]) treesort = Map.toAscList . Map.fromList main = B.interact $ uncsv . map treesort . csv Tillmann NOTICE: If received in error, please destroy and notify sender. Sender does not intend to waive confidentiality or privilege. Use of this email is prohibited when received in error. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Practise fingerspelling with Haskell! (Code cleanup request)
Dougal Stanton wrote: I think I will have to, sooner or later, become more versed in the subtle ways of non-IO monads. They seem to be capable of some seriously tricksy shenanigans. Keep trying. At some point you will achieve enlightenment in a blinding flash of light. Then you will write a monad tutorial. Everybody learning Haskell goes through this. In the hope of helping, here is *my* brief tutorial. Monads capture the pattern of do X then Y in context C. All other programming languages have a single fixed context built in, and almost all of them use the same one. This context is the reason that the order of X and Y matters: side effects are recorded in C, so stuff that happens in X is going to affect Y. Pure functions have no context, which means that X cannot affect Y (no context to transmit information). Which is great unless you actually want to say do X and then do Y. In order to do that you need to define a context for the side effects. Like I said earlier, most languages have exactly one context built in with no way to change it. Haskell has that context too: its called IO (as you may have guessed, these contexts are called monads in Haskell). The thing about Haskell is that you can substitute other contexts instead. Thats whats so great about monads. But since you have only ever programmed in languages that have the IO monad built in, the idea of replacing it with something else seems very strange. Ever programmed in Prolog? The backtracking that Prolog does is a different way of propogating side effects from one step to the next. Prolog provides a different context than most languages, and in Haskell you would describe it using a different monad. However because Prolog doesn't have monads it wasn't able to handle IO properly. Hence a backtracking computation with side effects in Prolog will repeat each side effect every time it gets reached. You could actually describe this in Haskell by defining a new monad with a backtracking rule but based on IO. Or you could have a different monad that only executes the side effects once the computation has succeeded. Each monad has two functions; return and = (known as bind). return says what it means to introduce some value into the context. Its really just there for the types, and in most cases its pretty boring. = describes how side effects propagate from one step to the next, so its the interesting one. The final (and really cool) thing you can do is glue a new monad together using monad transformers as a kit of parts. A monad transformer takes an inner monad as a type argument and the bind operation describes how effects in the inner monad are propagated in the outer monad. Thats a bit more advanced, but when you come to create your own monads its generally easier than building from scratch. Now I suggest going to http://en.wikibooks.org/wiki/Haskell/Understanding_monads and see if it makes any more sense. Ignore the nuclear waste metaphor if it doesn't work for you. The State monad is described about half way down, so you might think about that. State takes a type argument for the state variable, so side effects are restricted to changes in that variable. Hence State Integer is a monad with a state consisting of one integer. You might like to consider what could be done with random values in State StdGen. Hope this helps. Paul. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell-Cafe Digest, Vol 47, Issue 189
I wrote a short perl script to convert literate Haskell emails into pdf's. It requires lhs2TeX and pdflatex and might not work on Windows. You can darcs get http://rwf.mit.edu/~kyle/src/lhs-email/ I've tested it on a couple of articles from Oleg's FTP site - the source and pdf output are in the folder above (not checked into darcs). I wrote this in a few hours because I (personally) have trouble reading long articles in fixed-width fonts. I also like to print the longer emails to study offline. BE WARNED that this is written in hacked-up-outofcontrol-line-noise perl, so don't look at the source if that gives you seizures. The script might be tangentially related to this thread: http://thread.gmane.org/gmane.comp.lang.haskell.cafe/18020/focus=18020 --Kyle ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Minim interpreter
Newbie question: why does the following give Not in scope 'c' for the last line? string :: Parsec.Parser String string = do c - Parsec.letter do cs - string return c:cs Parsec.| return [c] (This is copied more or less rote from http://legacy.cs.uu.nl/daan/download/parsec/parsec.html , so I'm guessing there's some sort of command-line option I'm missing?) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Speedy parsing
Oh, I didn't realize how much of a difference it would make. Thanks a lot! -- Joseph Re -Original Message- From: Salvatore Insalaco [mailto:[EMAIL PROTECTED] Sent: Friday, July 20, 2007 12:21 PM To: Tillmann Rendel Cc: Re, Joseph (IT); haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Speedy parsing 2007/7/20, Tillmann Rendel [EMAIL PROTECTED]: Re, Joseph (IT) wrote: At this point I'm out of ideas, so I was hoping someone could identify something stupid I've done (I'm still novice of FP in general, let alone for high performance) or direct me to a guide,website,paper,library, or some other form of help. I think that your problem is simply an excess of lazyness :). foldr is too lazy: you pass huge structures to fold, that you evaluate anyway. Try to import Data.List and use foldl' (not foldl), that is strict. Being left fold, you probably need to rework a bit your functions (I tried to simply flip them, but the result of the program wereflipped too), but the time (and memory) difference is unbelievabl (foldl' is constant in memory allocation). Salvatore NOTICE: If received in error, please destroy and notify sender. Sender does not intend to waive confidentiality or privilege. Use of this email is prohibited when received in error. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Weird ghci behaviour?
On Unix-like OSes: If I run ghc test.hs and then run ghci test.hs, ghci fails to load up my code. I have to touch test.hs and then run ghci. I can understand ghci refusing to recompile something it thinks it has already compiled. But it appears to refuse to load it into an interactive session - which is less useful. In fact, removing test.hi makes ghci work again. This is ghc 6.6. Anyone else seeing this? -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Minim interpreter
On Fri, Jul 20, 2007 at 10:10:58PM +0200, Hugh Perkins wrote:
Newbie question: why does the following give Not in scope 'c' for the last
line?
I assume you meant
string :: Parsec.Parser String
string = do c - Parsec.letter
do cs - string
return c:cs
Parsec.| return [c]
Without adding that indentation, the second do cuts of the first block
and you get a rather different error.
The problem here is that the line beginning Parsec.| is lined up
with the first token after do, so layout adds a semicolon in front
of it, but a statement can't begin with an operator, so to avoid that
parse error the layout rules add the close brace and end the do block.
It parses like this:
string = ( do { c - Parsec.letter
; cs - string
; return c:cs
} )
Parsec.| (return [c]
The parse error rule is there so a do block will be closed by the end of
surrounding parens or braces, maybe it has other uses.
In any case, you really ought to use many1.
string = Parsec.many1 Parsec.letter
Brandon
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Minim interpreter
Kindof vaguely made a start on this, but cant quite see how to handle variables. I guess variables can be stored as a (Map.Map String Double), at least for a first draft? Then, I'm building up two hierarchies in parallel: - a set of parsec functions to parse the incoming string into a Program hierarchy - a set of data types to represent a program Then, there's a class called Eval containing a function eval which is instanced for each bit of the program hierarchy, so we simply call eval on the top level, and the program is executed. That works just fine as long as the only thing eval has to cope with is print statements (so eval has type IO ()), but I'm guessing the clean solution is to thread a Map.Map through that somehow? Solution so far: -- parsing hierarchy (pretty basic, but this bit doesnt seem particularly scary) string :: Parsec.Parser String string = Parsec.many1 Parsec.letter minimprint = do Parsec.string print Parsec.many1 (Parsec.char ' ') Parsec.char '' stringvalue - string Parsec.char '' return (Print stringvalue) -- program data type hierarchy data Program = ProgramLeaf Statement | ProgramTree Program Statement deriving(Show) data Statement = PrintStatement Print | AssignmentStatement Assignment deriving(Show) data Print = Print String deriving(Show) data Assignment = VarAssignment Variable Value | Increment Variable | Decrement Variable deriving(Show) data Variable = Variable String deriving(Show) data Value = ValueFromConstant Constant | ValueFromVariable Variable deriving(Show) newtype Constant = Constant Int deriving(Show) -- eval instances class Eval a where eval :: a - IO() instance Eval Program where eval (ProgramLeaf statement) = eval statement eval (ProgramTree program statement) = do eval program eval statement instance Eval Statement where eval ( PrintStatement print) = eval print eval ( AssignmentStatement assignment) = return () instance Eval Print where eval (Print value) = putStrLn value -- some code to test this minimparse minimsentence = case (Parsec.runParser minimprint () minimsentence) of (Right statement) - eval statement Left error - putStrLn(error: ++ show(error)) test = minimparse print \hello\ Running test correctly gives an output of hello, which is a good start. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Minim interpreter
Hugh Perkins wrote: That works just fine as long as the only thing eval has to cope with is print statements (so eval has type IO ()), but I'm guessing the clean solution is to thread a Map.Map through that somehow? You could do that but your code starts to become messy and you'll hit other limitations. The standard approach to this problem is to use a State monad. Since you are already using one monad, IO, you can can stack the monads using Monad transformers which makes them both available (although you will need to use liftIO, see below) import Control.Monad import Control.Monad.State import Data.Map type Env = Map String String type InterpM = StateT Env IO eval :: a - InterpM t instance Eval Print where eval (Print value) = liftIO $ putStrLn value You access and store the state using get and put. For example: eval (Variable s) = do s - get lookup the value and return it. There is a paper on using Monads with interpreters (http://web.cecs.pdx.edu/~mpj/pubs/modinterp.html) and an example described at http://www.haskell.org/haskellwiki/Libraries_and_tools/HJS. Mark ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Weird ghci behaviour?
Hi Dan, On Fri, Jul 20, 2007 at 02:12:12PM -0700, Dan Piponi wrote: On Unix-like OSes: If I run ghc test.hs and then run ghci test.hs, ghci fails to load up my code. I have to touch test.hs and then run ghci. I can understand ghci refusing to recompile something it thinks it has already compiled. But it appears to refuse to load it into an interactive session - which is less useful. In fact, removing test.hi makes ghci work again. This is ghc 6.6. Anyone else seeing this? Seems to work for me, on Linux/amd64: $ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.6 $ echo 'main = putStrLn Foo' q.hs $ ghc q.hs $ ghci -v0 q.hs Prelude Main main Foo Prelude Main Can you please give a complete testcase for the problem you're seeing? Also, exactly which OS/arch are you on? Thanks Ian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Minim interpreter
Ok, that got the variables working.
Example:
*Minim evaluateprog $ ProgramTree ( ProgramLeaf $ AssignmentStatement(
VarAssignment (Variable test) ( ValueFromConstant (Constant 3 (
PrintStatement (PrintValue( ValueFromVariable(Variable test
3.0
3.0
I'm having eval return the IO monad, the Map, and a Double. That means we
can use the same Eval class to evaluate for example the value of a Value.
Next step is either to get the parsing working for the functional eval
parts, or to get looping working.
Yes, I'm aware that this is Haskell 101 :-D
module Minim
where
import Char
import List
import Control.Monad
import Control.Monad.State
import Control.Monad.Reader
import qualified Text.ParserCombinators.Parsec as Parsec
import qualified Data.Map as Map
{-
program := statement
| statement program;
statement := assignment
| conditional
| goto
| tag;
| print
| input
assignment := (var is val) { assign a value to a variable }
| (++ var) { increment a variable }
| (-- var);{ decrement a variable }
val := constant | var;
var := any symbol;
constant := any number
conditional := (if test then statement else statement);
test := (val comp val)
| (test and test); { boolean AND}
| (test or test) {boolean OR}
| (not test);{boolean NOT}
comp := | | =;
goto := (goto tag); {go to}
tag := any symbol
print := (print string) | (print val); nl; {nl is new line}
input := (input var); {input the users response to
var}
string := any string;
-}
testtry = Parsec.try (Parsec.string hello)
Parsec.| Parsec.string help
string :: Parsec.Parser String
string = Parsec.many1 Parsec.letter
minimprint = do Parsec.string print
Parsec.many1 (Parsec.char ' ')
Parsec.char ''
stringvalue - string
Parsec.char ''
return (Print stringvalue)
parens :: Parsec.Parser ()
parens = do Parsec.char '('
parens
Parsec.char ')'
parens
Parsec.| return ()
class Eval a where
eval :: a - StateT (Map.Map String Double) IO Double
data Program = ProgramLeaf Statement | ProgramTree Program Statement
deriving(Show)
instance Eval Program where
eval (ProgramLeaf statement) = eval statement
eval (ProgramTree program statement) = do eval program
eval statement
data Statement = PrintStatement Print |
AssignmentStatement Assignment
deriving(Show)
instance Eval Statement where
eval ( PrintStatement print) = eval print
eval ( AssignmentStatement assignment) = eval assignment
data Print = Print String | PrintValue Value
deriving(Show)
instance Eval Print where
eval (Print value) = do liftIO $ putStrLn value
return 0
eval (PrintValue value) = do evaluatedvalue - eval value
liftIO $ putStrLn (show(evaluatedvalue))
return evaluatedvalue
data Assignment = VarAssignment Variable Value |
Increment Variable |
Decrement Variable
deriving(Show)
instance Eval Assignment where
eval (VarAssignment (Variable varname) (ValueFromConstant (Constant
constant))) = do oldmap - get
let newmap = Map.insert varname constant oldmap
put newmap
return constant
data Variable = Variable String
deriving(Show)
data Value = ValueFromConstant Constant | ValueFromVariable Variable
deriving(Show)
instance Eval Value where
eval (ValueFromConstant (Constant i )) = return i
eval (ValueFromVariable (Variable varname )) = do map - get
return (map Map.!
varname)
newtype Constant = Constant Double
deriving(Show)
instance Eval Constant where
eval (Constant i) = return i
evaluateprog prog = evalStateT( eval prog ) Map.empty
minimparse minimsentence = case (Parsec.runParser minimprint ()
minimsentence) of
(Right statement) - evaluateprog statement
Left error - do putStrLn(error: ++
show(error))
return 0
test = minimparse print \hello\
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] i need wxHaskell compiled for ghc 6.6.1 on Windows
Hi Bulat, can anyone provide wxHaskell already compiled/compilable with ghc 6.6.1 on Windows? Please try the darcs version darcs get http://darcs.haskell.org/wxhaskell It's probably simplest to get it working with wxWidgets 2.6.4 http://prdownloads.sourceforge.net/wxwindows/wxMSW-2.6.4-Setup.exe Best, -- Eric Kow http://www.loria.fr/~kow PGP Key ID: 08AC04F9 Merci de corriger mon français. pgpMW52c9Enq4.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
