- Haskell-Cafe - Haskell.org

Could not deduce .. why ?
by Marc Weber 12 Oct '08

12 Oct '08

Surely I've overseen a small point. But I can't see it: Why doesn't ghc recognize taht elc_ (class decl), elc (instance decl) and elc_1 are the same type To help you find the connecting pieces faster I've marked them with ## ## Marc data PT a b = PT b -- phantom type containing state a and the result b class AddEl el_ el2_ elc_ where addEl :: el_ -> elc -> el2_ -- el, child -- ========== adding sub elements (tags) ============================= class AddElT est el_ estc ##elc_## est2 el2_ | estc est -> est2 , est est2 estc el2_ -> el_ , est est2 estc el2_ -> elc_ where addElT :: PT est el_ -> PT estc ##elc_## -> PT est2 el2_ -- first child ? attrs ok? instance ( AddEl el el2 ##elc## <-- this is not recognized because elc != elc_1 , Consume st (Elem celType) st' , DetermineElAddEl (NYV (Element elType AttrsOk st HFalse)) el (Valid celType) elc (NYV (Element elType AttrsOk st' HTrue)) el2 ) => AddElT (NYV (Element elType AttrsOk st HFalse)) el (Valid celType) ##elc## <-- elc_ from class declaration (NYV (Element elType AttrsOk st' HTrue)) el2 where addElT (PT t) (PT ##c##) = PT $ addEl t c -- <<<<<<<<< line 435, c should have type elc, not elc_1 src/Text/XML/Validated/Types.hs|435 col 32 error| || Could not deduce (AddEl el el2 elc_1) || from the context (AddElT || (NYV (Element elType AttrsOk st HFalse)) || el || (Valid celType) || elc || (NYV (Element elType AttrsOk st' HTrue)) || el2, || AddEl el el2 elc, || Consume st (Elem celType) st', || DetermineElAddEl || (NYV (Element elType AttrsOk st HFalse)) || el || (Valid celType) || elc || (NYV (Element elType AttrsOk st' HTrue)) || el2) || arising from a use of `addEl' || at src/Text/XML/Validated/Types.hs:435:32-40 || Possible fix: || add (AddEl el el2 elc_1) to the context of the instance declaration || In the second argument of `($)', namely `addEl t c' || In the expression: PT $ addEl t c || In the definition of `addElT': || addElT (PT t) (PT c) = PT $ addEl t c

2 1

How to translate Haskell to other languages?
by Jason Dagit 12 Oct '08

12 Oct '08

Hello, I was thinking about translating Haskell to other languages, python being the main one at the moment. Here is my attempt at manually encoding Haskell in Python: \begin{code} import types class thunk: '''Thunks allow us to delay a computation and they also store their value inside themselves once they have been accessed.''' def __init__(self, v): self.v = v def value(self): '''Force the thunk to be calculated by referencing it.''' while self.isReducible(): self.reduce() return self.v def reduce(self): '''Reduces the thunk, by either calling the represented function or reducing the layers of thunk.''' if (type(self.v) == types.FunctionType): self.v = self.v() else: self.v = self.v.value() return self.v def isReducible(self): '''Returns True when the thunk is still callable.''' return isinstance(self.v, thunk) or \ type(self.v) == types.FunctionType class nil: '''Empty list element''' def __init__(self): pass class cons: '''Non-empty lists''' def __init__(self, head, tail): self.head = head self.tail = tail '''Unpack the cons cell''' def uncons(self): return self.head, self.tail def htail(t): '''This function works like Haskell's tail function.''' l = t.value() x, xs = l.uncons() return xs def plus(t1, t2): '''Adds numbers''' i1 = t1.value() i2 = t2.value() return thunk(i1+i2) def zipWith(f, t1, t2): '''This is like Haskell's zipWith function.''' l1 = t1.value() if isinstance(l1, nil): return thunk(nil()) l2 = t2.value() if isinstance(l2, nil): return thunk(nil()) x, xs = l1.uncons() y, ys = l2.uncons() zw = thunk(lambda: zipWith(f, xs, ys)) fxy = thunk(lambda: f(x,y)) return thunk(cons(fxy, zw)) def fibs(): '''This is the classic fibs: fibs = 1 : 1 : zipWith (+) fibs (tail fibs)''' f1 = thunk(1) f2 = thunk(1) fn = thunk(fibs) rest = thunk(lambda: zipWith(plus, fn, htail(fn))) restlist = thunk(cons(f2, rest)) fiblist = thunk(cons(f1, restlist)) return fiblist def hmap(f, t): '''map _ [] = [] map f (x:xs) = f x : map f xs''' l = t.value() if isinstance(l, nil): return thunk(nil()) x, xs = l.uncons() fx = thunk(lambda: f(x)) mapfxs = thunk(lambda: hmap(f, xs)) return thunk(cons(fx, mapfxs)) def show(t): '''show :: a -> String''' v = t.value() return thunk(str(v)) def printList(t): '''This just gives us a way to debug lists.''' v = t.value() print "[", while True: h,t = v.uncons() print "%s" % h.value(), if isinstance(t.value(), nil): break else: print ", ", v = t.value() print "]" def take(tn, tl): '''take n _ | n <= 0 = [] take _ [] = [] take n (x:xs) = x : take (n-1) xs''' n = tn.value() if n <= 0: return thunk(nil()) l = tl.value() if isinstance(l, nil): return thunk(nil()) x,xs = l.uncons() nminusone = thunk(lambda: plus(tn, thunk(-1))) takerec = thunk(lambda: take(nminusone, xs)) return thunk(cons(x, takerec)) \end{code} You can try this out in python with: tenfibs = take(thunk(10), fibs()) printList(tenfibs) This will print the first 10 fibs. Questions: I think the examples above are correctly lazy. Have I missed something? I noticed my thunks can get wrapped in each other, is this to be expected, or am I doing it wrong? Is there an easier encoding using generators? When I started I was using generators instead of thunk, but I found it was complicating my design so I removed it. And yet, since generators are python's version of thunks, it seems like there should be a more natural encoding there. I'm not explicitly using a graph reduction algorithm to reach WHNF, does this mean my translation is wrong? Are there some well known test cases I should try? Anyone know of a paper that discusses making this translation? I am trying to avoid writing an interpreter in Python for Haskell. My goal is to translate Haskell functions into the equivalent Python. I'm also hoping to avoid needing a G-machine. Thanks! Jason

6 6

Shooting your self in the foot with Haskell
by John Van Enk 12 Oct '08

12 Oct '08

There's the well known "How to shoot your self in the foot" list which I have it printed and taped on my desk at work. http://www-users.cs.york.ac.uk/susan/joke/foot.htm I had a co-worker ask me how you'd shoot your self in the foot with Haskell. Here's the best I could do: "You shoot the gun, but the bullet gets trapped in the IO monad." I fully realize how un-clever this is. Some one please give me something more worth of the original list. :) -- /jve

18 24

Real World Haskell Chapter 11 ... Testing
by Galchin, Vasili 12 Oct '08

12 Oct '08

Hi, Testing of "pure" code ... . way cool ... I am sure there literature from the first order logic, model theory, categorical logic viewpoint?? Kind regards, Vasili

1 0

[] vs [()]
by Daryoush Mehrtash 12 Oct '08

12 Oct '08

What is the difference between empty list [] and list with one unit element [()]? daryoush

10 12

OT: Haskell desktop wallpaper?
by Magnus Therning 11 Oct '08

11 Oct '08

This morning I got tired of my desktop wallpaper (one that ships with Debian's Gnome packages). Typing "haskell desktop wallpaper" yeilded a lot of links to wallpapers with Colleen Haskell, while she's a beautiful lady it wasn't exactly what I was hoping to find. Hence this email. Where can I find some nice wallpapers inspired by Haskell, or maybe even created by Haskell code? Oh yes, wallpapers related to XMonad would do, I suppose ;-) /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe

10 13

External Sort and unsafeInterleaveIO
by Ben 11 Oct '08

11 Oct '08

hi folks -- a haskell newbie here, searching for comments and wisdom on my code. i had a project to try to implement "external sort" in haskell as a learning exercise. (external sort is sorting a list that is too large to fit in main memory, by sorting in chunks, spooling to disk, and then merging. more properly there probably should be multiple stages, but for simplicity i'm doing a one-stage external sort.) the trick is the number of files can quickly grow very large, so it is best to use one large file and seek inside it around. however as one can imagine the order-of-IO-operations becomes a bit tricky, if you're seeking file handles around underneath Data.ByteString.Lazy's nose. but late this night after not thinking about it for a while i had a brainstorm: rewrite hGetContents to keep the handle position in the right place! it's all about judicious use of unsafeInterleaveIO..... it seems to be rather fast, strangely faster than the usual "sort" at times. it also seems to have nice memory characteristics, though not perfect. it's hard to test because the normal "sort" function takes too much RAM on large lists, making my computer swap like mad. i'd appreciate any testing, comments and suggestions from the haskell gods out there. my thanks to the Data.ByteString.Lazy, Data.Binary, and Data.Edison people, who made this rather easy, once I grokked unsafeInterleaveIO. thanks and take care, B > module ExternalSort where Sort a list of Ords "offline." We're doing this to be able to sort things without taking up too much memory (for example sorting lists too large to fit in RAM.) Laziness is imperative, as is the order-of-operations. > import Control.Monad > import Data.List > import qualified Data.Binary as Bin > import qualified Data.ByteString.Lazy as B > import qualified Data.ByteString as P (hGetNonBlocking, null) > import Data.ByteString.Base (LazyByteString(LPS)) > import Foreign.Storable (sizeOf) > import System.IO (openFile, hClose, hSeek, hTell, hIsEOF, hWaitForInput, > Handle, IOMode(ReadMode, WriteMode), > SeekMode(AbsoluteSeek)) > import System.IO.Unsafe (unsafeInterleaveIO) > > import qualified Data.Edison.Seq.ListSeq as LS > import qualified Data.Edison.Coll.SplayHeap as Splay Conceptually, we sort a list in blocks, spool blocks to disk, then merge back. However for IO performance it is better to read off chunks of elements off the sorted blocks from disk instead of elements-at-a-time. It would be better if these were in KBytes instead of # of elements. > blocksize :: Int > blocksize = 10000 Turn a list into a list of chunks. > slice :: Int -> [a] -> [[a]] > slice _ [] = [] > slice size l = (take size l) : (slice size $ drop size l) Turn a list into a list of blocks, each of which is sorted. > blockify :: (Ord a) => Int -> [a] -> [[a]] > blockify bsize l = map sort $ slice bsize l Serialize a block, returning the (absolute) position of the start. > dumpBlock :: (Ord a, Bin.Binary a) => Handle -> [a] -> IO Integer > dumpBlock h b = do > start <- hTell h > B.hPut h $ Bin.encode b > return start The actual sorting function. We blockify the list, turning it into a list of sorted blocks, and spool to disk, keeping track of offsets. We then read back the blocks (lazily!), and merge them. > externalSort [] = do return [] > externalSort l = do > h <- openFile "ExternalSort.bin" WriteMode > idx <- mapM (\x -> dumpBlock h x) (blockify blocksize l) > hClose h > h <- openFile "ExternalSort.bin" ReadMode > blocks <- mapM (\x -> do {bs <- hGetContentsWithCursor h x; > return $ Bin.decode bs}) idx > return (kMerge $ blocks) Merging chunks. K-way merge (and in fact external sort in general) is detailed in Knuth, where he recommends tournament trees. The easiest thing is to probably use one of Okasaki's heaps. I'll use splay heaps, because I don't know any better. It would be better if I changed Ord for blocks to only check the first element. > kMerge :: (Ord a) => [[a]] -> [a] > kMerge [] = [] > kMerge l = > let h = Splay.fromSeq l in > kM (Splay.minElem h) (Splay.deleteMin h) > where > kM :: (Ord a) => [a] -> Splay.Heap [a] -> [a] > kM l h > | h == Splay.empty = l > | otherwise = > let next = Splay.minElem h > (f, b) = span (\x -> x <= head next) l > in > f ++ (kM next (if null b then Splay.deleteMin h > else (Splay.insert b $ Splay.deleteMin h))) > > kMergeSort :: (Ord a) => [a] -> [a] > kMergeSort l = kMerge $ blockify blocksize l This is a version of hGetContents which resets its handle position between reads, so is safe to use with interleaved handle seeking. > hGetContentsWithCursor :: Handle -> Integer -> IO B.ByteString > hGetContentsWithCursor = hGetContentsWithCursorN defaultChunkSize > > hGetContentsWithCursorN :: Int -> Handle -> Integer -> IO B.ByteString > hGetContentsWithCursorN k h start = (lazyRead start) >>= return . LPS > where > lazyRead start = unsafeInterleaveIO $ loop start > > loop start = do > hSeek h AbsoluteSeek start > ps <- P.hGetNonBlocking h k > --TODO: I think this should distinguish EOF from no data available > -- the otherlying POSIX call makes this distincion, returning either > -- 0 or EAGAIN > if P.null ps > then do eof <- hIsEOF h > if eof then return [] > else hWaitForInput h (-1) > >> (loop start) > else do > pos <- hTell h > pss <- lazyRead pos > return (ps : pss) > > defaultChunkSize :: Int > defaultChunkSize = 32 * k - overhead > where k = 1024 > overhead = 2 * sizeOf (undefined :: Int)

5 6

Re: [Haskell-cafe] Haskell in Artificial Intelligence
by Chryssochoidis Christos 11 Oct '08

11 Oct '08

On 11 Οκτ 2008, at 10:57 ΠΜ, Krasimir Angelov wrote: > Hi Christos > > We use Haskell for natural language processing. See here: > > http://www.cs.chalmers.se/~aarne/GF/ > > Best regards, > Krasimir > Thank you very much for your response Krasimir. Best regards, Christos > On Fri, Oct 10, 2008 at 8:45 PM, Christos Chryssochoidis > <c.chryssochoidis(a)gmail.com> wrote: >> Greetings, >> >> I'm interested in doing a survey about the use of Haskell in the >> field of >> Artificial Intelligence. I searched in Google, and found in the >> HaskellWiki, >> at www.haskell.org/haskellwiki/Haskell_in_industry, two >> organizations that >> use Haskell and do work related to AI. Besides that, I haven't >> found much >> else. Could somebody from the Haskell community give me some >> pointer to a >> project or system related to AI that uses Haskell? >> >> Thank you very much in advance. >> >> - CC >> >> >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >>

1 0

Re: [Haskell-cafe] Interesting new user perspective
by Donn Cave 11 Oct '08

11 Oct '08

Quoth John Goerzen <jgoerzen(a)complete.org>: | Uh... yes. Opening and closing files, command-line parsing, etc -- | needed by almost every program. Aside from some very simple | stdin-to-stdout filters, it is difficult to imagine a program where | you don't need to open a file! That's how it seems to me, too, and moreover maybe the most generally recognizable API. With a GUI or a database, you're going to need to present a fair amount of background to just about everyone, but files, command lines etc. are common to nearly every programming language. If the virtues of Haskell can't be presented in this context, then maybe it isn't such a generally useful language that people ought to be worried about learning it. Donn Cave, donn(a)avvanta.com

1 0

ANNOUNCE: maccatcher-1.0.0
by Jason Dusek 10 Oct '08

10 Oct '08

This simple little package obtains a MAC address on *NIX and Windows. It is known to work on Linux, OS X and Windows XP. There is no C fanciness in this package -- it relies on shell commands. The MAC is cached after the first query, using an IORef (I am open to other ideas, but this seemed sufficient). -- _jsn |This simple little package...| http://hackage.haskell.org/cgi-bin/hackage-scripts/package/maccatcher-1.0.0

2 2