March 2007 - Haskell-Cafe

Two Other AI Sources
by Adam Wyner 20 Mar '07

20 Mar '07

For the Haskell and AI work, we ought to consider AI programming books in addition to Russell and Norvig: /Paradigms of AI Programming: Case Studies in Common Lisp/, P. Norvig, 1991. /Prolog Programming for Artificial Intelligence/, I. Bratko, 1990./ Artificial Intelligence Techniques in Prolog/, Y. Shoham, 1994. Perhaps there are newer additions (e.g. Bratko), but the problems and solutions from these languages are presented. We can build on them rather than starting from scratch or even just the theoretical outline of Russell and Norvig. Adam

5 5

Search monad
by Edsko de Vries 20 Mar '07

20 Mar '07

Hey, I have a structure containing Xs in various places, like so data X data Structure = Structure .. [X] .. [X] .. And I defined mapStructure mapStructure :: (X -> X) -> (Structure -> Structure) I then wanted to use mapStructure to define queries as well as transformations on structures. I generalized mapStructure to mapStructureM: mapStructure :: Monad m => (X -> m X) -> (Structure -> m Structure) and then defined the following search monad: > data Search f a b = Found (f a) b > > class Monad (m a) => SearchMonad m a where > found :: a -> m a a > > fromSearch :: Search f a b -> f a > fromSearch (Found a _) = a > > search :: (SearchMonad m a) => (a -> Bool) -> a -> m a a > search f a > | f a = found a > | otherwise = return a Instances of the monad for finding one and for finding all elements: > instance SearchMonad (Search Maybe) a where > found a = Found (Just a) a > > instance SearchMonad (Search []) a where > found a = Found [a] a > > instance Monad (Search Maybe a) where > return b = Found Nothing b > Found (Just a) a' >>= f = case f a' of > Found _ b -> Found (Just a) b > Found Nothing a' >>= f = f a' > > instance Monad (Search [] a) where > return b = Found [] b > Found as a' >>= f = case f a' of > Found as' b -> Found (as ++ as') b Here is a simple sample session with ghci *Util> fromSearch $ mapM (search even) [1,3,5] :: Maybe Int Nothing *Util> fromSearch $ mapM (search even) [1,2,3,4,5] :: Maybe Int Just 2 *Util> fromSearch $ mapM (search even) [1,2,3,4,5] :: [Int] [2,4] What I'm wondering about is if this monad is an instance of a more general monad(if so, which one?), and generally if people have any comments about these definitions. Thanks! Edsko

4 3

wanted: haskell one-liners (in the perl sense of one-liners)
by Thomas Hartman 20 Mar '07

20 Mar '07

Okay, I am aware of http://haskell.org/haskellwiki/Simple_unix_tools which gives some implementation of simple unix utilities in haskell. But I couldn't figure out how to use them directly from the shell, and of course that's what most readers will probably wnat. Or let me put it another way. Is there a way to do find -maxdepth 1 -type f | xargs du | perl -ane 'print "\$F[0]\n"' | perl -e '$sum += $_ while <>; print "$sum\n"' as a shell command that idiomatically uses haskell? For non-perlers, that sums up the disk usage of all files in the current directory, skipping subdirs. print "\$F[0]\n looks at the first (space delimited) collumn of output. perl -e '$sum += $_ while <>; print "$sum\n"' , which is I guess the meat of the program, sums up all the numbers spewed out of the first column, so in the end you get a total. So, anyone out there want to establish a haskell one liner tradition? :) thomas.

11 25

Re: [Haskell-cafe] Re: wanted: haskell one-liners (in the perl sense of one-liners)
by Thomas Hartman 20 Mar '07

20 Mar '07

You contributed #12:14 < Thunder> @pl \s -> drop (length s - n) s #12:14 < lambdabot> drop =<< subtract n . length But, on second thought, 1) I can't use this as a drop-in replacement for the non points free (right term?) version, and 2) I don't really understand it. Still, I would be curious to see if there is a way to make this useful somehow. 2007/3/20, Lutz Donnerhacke <lutz(a)iks-jena.de>: > In iks.lists.haskell, you wrote: > > This takes a long file containing mostly numerical data, filters out > > the numerical data, and sorts it numerically. (Not the same thing as > > sorting alphabetically, which is what you get by default, or using the > > unix sort utility). Maybe there's some flag to make unix sort util act > > like this? Enh, who cares, now we have haskell. :) > > sort -g > > > Thanks to Thunder > > I was not that helpful. >

2 1

Haskell-cafe] Haskell and a new web developement mailinglist?
by Dimitry Golubovsky 20 Mar '07

20 Mar '07

Marco Weber wrote: >I've been talking to Chris Eidhof the last days and we'd like to suggest adding >another specialized haskell mailinglist: Haskell and web developement. I support the idea to have such a mailing list. Thanks. -- Dimitry Golubovsky Anywhere on the Web

1 0

NYTimes.com: John W. Backus, 82, Fortran Developer, Dies
by paul.hudak＠yale.edu 20 Mar '07

20 Mar '07

This page was sent to you by: paul.hudak(a)yale.edu. John Backus, inventor of Fortran, Turing Award winner, and also an early pioneer in functional programming, died Saturday at his home in Oregon. Many of us have fond memories of him in the earlier days of our careers, and we all owe a lot to him for giving credibility to functional programming through his Turing Award lecture, "Can Programming Be Libarated From the von Neumann style?" Here is an article from the New York Times. BUSINESS | March 20, 2007 John W. Backus, 82, Fortran Developer, Dies By STEVE LOHR Mr. Backus assembled and led the I.B.M. team that created Fortran, the first widely used programming language. http://www.nytimes.com/2007/03/20/business/20backus.html?ex=1175054400&en=d… ---------------------------------------------------------- ABOUT THIS E-MAIL This e-mail was sent to you by a friend through NYTimes.com's E-mail This Article service. For general information about NYTimes.com, write to help(a)nytimes.com. NYTimes.com 500 Seventh Avenue New York, NY 10018 Copyright 2007 The New York Times Company

1 0

Re: [Haskell-cafe] what I learnt from my first serious haskell programm
by Fawzi Mohamed 20 Mar '07

20 Mar '07

oops, I realized now that my answer did not go to the list. For the record here is it: Thanks to everybody for the answers and to Henning Thielemann for the useful links: > http://haskell.org/haskellwiki/Qualified_names > > http://haskell.org/haskellwiki/Category:Style > I agree with apfelmus that recursive module should be supported (as the standard requires) this would make it easier to use one module per main type (the distributed approach), this approach was also what I had in mind, but it comes very close to introducing by hand one namespace per type from which came my rant about missing namespaces... Fawzi

1 0

ANN: MIME Strike Force
by Jeremy Shaw 20 Mar '07

20 Mar '07

Hello, If you have tried to do any MIME processing using Haskell, you are likely to have found two things: 1) There are a lot of MIME libraries for Haskell 2) None of them do everything you want So, I propose that we form a MIME Strike Force and create the one, true MIME library. The plan is something like this: 1) Document all the things the MIME library needs to support. 2) Pick the technology, and design the infrastructure for supporting these features. For example, I don't think we will be able to use Parsec because: i) We want to support ByteString ii) We want to be able to lazily parse the message 3) Try to reuse as much existing code as possible to implement the design. I have started step 1 by creating this page: http://www.haskell.org/haskellwiki/Libraries_and_tools/MIMEStrikeForce Please add your comments, requirements, etc. If you are interesting in helping contrib ideas, code, or flames, please let me know. If there is enough interest, we should probably set up a mailing list for discussion. j. ps. This *might* make a decent SoC project, but only if it results in the one, true MIME library. We definitely do not need another incomplete MIME library floating around.

4 3

Matrices in Haskell
by Ivan Miljenovic 20 Mar '07

20 Mar '07

Some of you might recall me annoying people on #haskell over the New Year about my Latin Squares project. Well, I'm looking at re-doing it from scratch, but the first thing I need to do is find a new way of representing my square. I have been using a list of lists ([[a]]) to represent a matrix. The problem with this data structure is that I need to be able to manipulate matrices as both row-oriented and column-oriented data structures, as I need to examine the values in the columns as well as in the rows. As it stands, I was doing this by transposing the matrix, manipulating it, then transposing it back again. This is a pain, as it takes up about 15% to 20% of the run time. The other problem with using a list of lists is that the only reason I'm sure that the matrix is valid (i.e. all the rows are the same length, etc.) is because I created it that way, not because the data structure requires it. As such, I'd like to know if there's any way of storing a an n-by-n matrix such that the algorithm/function to get either the rows or the columns is less than O(n^2) like transposition is. I did try using an Array, but my (admittedly hurried and naive) usage of them took longer than a list of lists, was more difficult to manipulate, and wasn't required separate inverse functions to row and cols. Also, since I need to look all throughout the list of values, it's still O(n^2), but this time for both rows and columns. I know that when doing something similar to this in Java a few years ago (a primitive Sudoku solver, to be precise), I could represent the rows and columns as to separate 2D arrays, with rows(i,j) pointing to the same object as cols(j,i). Is something like this possible in Haskell? in particular, I will be storing lists of possible values in the cells of the matrix, so the capability to backtrack would be very nice, as I'd be trying each value at a time to see if it is valid. I'd also want to use such a matrix implementation next semester for a project, which I plan on being a quick comparison of various programming languages as to ease of use and efficiency for matrix-based computing problems. -- Ivan Lazar Miljenovic

6 10

Re: There can be only one fix? Pondering Bekic's lemma
by oleg＠pobox.com 20 Mar '07

20 Mar '07

Nicolas Frisby wrote: > My question is: Given products and a fixed point combinator, can any > pure expression be transformed into a corresponding expression that > has just a single use of fix? Albert Y. C. Lai pointed out model-theoretical and CPU-practical answers. There is also a Haskell-automatic answer. That is, polyvariadic fixpoint, a combinator to obtain a mutually least fixpoint of several terms, is expressible in Haskell itself, via the regular fix: http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic I like its inferred type fix':: [[a->b]->a->b] -> [a->b] which is truly the type of the (applicative, or eta-expanded) regular fix with some round parentheses replaced with square ones.

1 0