December 2008 - Haskell-Cafe

The Knight's Tour: solutions please
by oleg＠okmij.org 02 Dec '08

02 Dec '08

Yes, there is a solution for n=99 and for n=100 for that matter -- which can be found under one second. I only had to make a trivial modification to the previously posted code > tour n k s b | k > n*n = return b > | otherwise = do next <- (foldr mplus mzero).map return $ successors n b s > tour n (k+1) next $ insrt next k b I replaced foldl1 mplus with foldr mplus zero. Here are the results: for n=99, the first line of the board is 1 4 2885 214 309 6 311 216 307 8 315 218 305 10 319 220 303 12 2021 222 301 14 1727 224 299 16 1699 226 297 18 1561 228 295 20 1247 230 293 22 1227 232 291 24 1165 234 289 26 1007 236 287 28 965 238 285 30 775 240 283 32 759 242 281 34 625 244 279 36 559 246 277 38 543 248 275 40 455 250 273 42 435 252 271 44 407 254 269 46 377 256 267 48 365 258 65 50 63 60 67 52 55 time is 0m0.730s n=100 1 4 205 9996 209 6 207 9940 211 8 9897 9900 213 10 9895 9906 215 12 9809 9880 217 14 9807 9740 219 16 9799 9072 221 18 8445 8864 223 20 8443 8378 225 22 8347 8352 227 24 8331 7860 229 26 7863 7844 231 28 7749 7754 233 30 7735 7742 235 32 7733 7320 237 34 677 640 239 36 597 568 241 38 535 540 243 40 517 500 245 42 473 452 247 44 371 358 249 46 305 310 251 48 293 286 253 50 291 270 255 52 259 262 time is 0m0.373s For n=101, time is 0m0.388s wren ng thornton wrote: > FWIW, fair choice (interleave) is much slower than unfair choice (mplus) > in logict. Unfortunately this means you need to know a lot about the > problem domain to correctly choose between them when maximal performance > is at stake; just using fair choice everywhere costs too much for many > problems. I believe that FBackTrack relieves one from making the above choice: the ordinary mplus is FBackTrack is both fair and speedy. There is no longer any need for interleave; btw, interleave does not ensure completeness, whereas FBackTrack, I conjecture, implements a complete search procedure: if there is a solution, FBackTrack will eventually find one. The only `drawback' of using FBackTrack is that the order of the answers (if there are several) is essentially unpredictable. Informally, the answers are delivered in the order of the difficulty of finding them. This drawback is relative however: if we insist that the sequence of answers of (m1 `mplus` m2) is the concatenation of the sequences of answers of m1 and then m2, our search procedure is incomplete.

3 2

Sugestion for a basic Utf8 type.
by Mauricio 02 Dec '08

02 Dec '08

Hi, I would like to sugest a new basic type in Haskell. What if we had something like this (with any other quoting character): «Je ne parle pas français. Meu nome é Maurício. ¿Hablas español?» This would be of type Utf8. I think now it is not a bad idea, since Haskell source code is supposed to be utf-8. The internal representation of this datatype would be a null terminated utf-8 byte vector. No standard operations would be defined on that type, i.e., it would be a “communication standard” between everybody, but module writers could develop different basic usage based on operations on them using Foreign. (I think it would be dificult to set default operations, since there are so many things you can do with utf-8.) Pros: * There would be no doubt you can use utf-8 when using this, since there's no conversion involved. * Cleaner code on utf8 operations, maybe. There are many utf8 modules today with different goals in mind, I thing it would be nice if they could share this common basic type and a common underline implementation. Cons: * Probably, many. I have no deep understanding of Haskell. Thanks for your attention, Maurício

3 5

import
by Galchin, Vasili 02 Dec '08

02 Dec '08

Hello, I am a little uncertain about "import" semantics in a hierarchical package ... i.e. if I import the root of a package root do I get everything under the "root's" namespace, i.e. the namespace tree? thanks, vasili

3 4

ANNOUNCE: Haskell Communities and Activities Report (15th ed., November 2008)
by Janis Voigtlaender 02 Dec '08

02 Dec '08

On behalf of the many, many contributors, I am pleased to announce that the Haskell Communities and Activities Report (15th edition, November 2008) http://www.haskell.org/communities/ is now available from the Haskell Communities home page in PDF and HTML formats. Many thanks go to all the people that contributed to this report, both directly, by sending in descriptions, and indirectly, by doing all the interesting things that are reported. I hope you will find it as interesting a read as I did. If you have not encountered the Haskell Communities and Activities Reports before, you may like to know that the first of these reports was published in November 2001. Their goal is to improve the communication between the increasingly diverse groups, projects, and individuals working on, with, or inspired by Haskell. The idea behind these reports is simple: Every six months, a call goes out to all of you enjoying Haskell to contribute brief summaries of your own area of work. Many of you respond (eagerly, unprompted, and sometimes in time for the actual deadline ;-) to the call. The editor collects all the contributions into a single report and feeds that back to the community. When I try for the next update, six months from now, you might want to report on your own work, project, research area or group as well. So, please put the following into your diaries now: ---------------------------------------- End of April 2009: target deadline for contributions to the May 2009 edition of the HC&A Report ---------------------------------------- Unfortunately, many Haskellers working on interesting projects are so busy with their work that they seem to have lost the time to follow the Haskell related mailing lists and newsgroups, and have trouble even finding time to report on their work. If you are a member, user or friend of a project so burdened, please find someone willing to make time to report and ask them to "register" with the editor for a simple e-mail reminder in April (you could point me to them as well, and I can then politely ask if they want to contribute, but it might work better if you do the initial asking). Of course, they will still have to find the ten to fifteen minutes to draw up their report, but maybe we can increase our coverage of all that is going on in the community. Feel free to circulate this announcement further in order to reach people who might otherwise not see it. Enjoy! Janis Voigtlaender <hcar at haskell.org> -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

3 2

What causes <<loop>>?
by Martin Hofmann 02 Dec '08

02 Dec '08

I am picking up a discussion with the same topic from haskell-users on 8th November. Thunks with reference on themselves was mentioned as main reason for <<loop>>. > A safe recursive definition would be > let x = Foo (x+1) > However, if you leave out the constructor, > let x = x + 1 > you get a <<loop>> (or a deadlock). > Are there any other reasons? I am trying to debug monadic code which stores state information in a record maintaining several Data.Maps, but in vein so far. A state is modified/changed in several steps by a compound function i.e. changeA $ changeB $ changeC state Is code using mtl, records or Maps more prone to <<loop>> or does this not matter at all. How can I identify self-referencing thunks more easily? Is there any rule of thumb to prevent <<loop>>? Are there any less obvious newbie mistakes causing <<loop> then the one above? Any comments, experience, and tips are highly appreciated. Thanks, Martin

1 0

serious defect in system-uuid
by Jason Dusek 02 Dec '08

02 Dec '08

I discovered that my UUID type causes a <<loop>> when tested for equality. Anyone who is using `system-uuid`, please upgrade to version 1.0.2. -- _jsn

1 0

System.IO.UTF8 Problem
by Ben George 02 Dec '08

02 Dec '08

Hi, so I've been working with System.IO.UTF8 trying to get it to render Japanese characters correctly. Using just IO I've gotten it to output the correct unicode values, however, replacing the IO.putStrLn commands with System.IO.UTF8 yielded some strange errors. I went through the program and replaced the System.IO.UTF8 putStrLn and hGetLine commands with their "normal" IO counterparts, however, simply having the "import System.IO.UTF8" line at the beginning of the file causes an error during compilation. $ghc file.hs compilation IS NOT required byteindex.o: In function `sKE_info': (.text+0x8bf): undefined reference to `__stginit_utf8zmstringzm0zi3zi3_SystemziIOziUTF8_' collect2: ld returned 1 exit status Below is the output of ghc -v. I am running Ubuntu 7.10 gutsy. I have been getting the same error whether GHC was compiled from binaries or source. Currently I am running GHC (version 6.8.3) compiled from source. $ ghc -v file.hs Glasgow Haskell Compiler, Version 6.8.3, for Haskell 98, stage 2 booted by GHC version 6.8.3 Using package config file: /usr/local/lib/ghc-6.8.3/package.conf wired-in package base mapped to base-3.0.2.0 wired-in package rts mapped to rts-1.0 wired-in package haskell98 mapped to haskell98-1.0.1.0 wired-in package template-haskell mapped to template-haskell-2.2.0.0 wired-in package ndp not found. Hsc static flags: -static Created temporary directory: /tmp/ghc6586_0 *** Checking old interface for main:Main: compilation IS NOT required *** Touching object file: touch byteindex.o *** Linker: gcc -v -o a.out -DDONT_WANT_WIN32_DLL_SUPPORT byteindex.o -L/usr/local/lib/ghc-6.8.3/lib/haskell98-1.0.1.0 -L/usr/local/lib/ghc-6.8.3/lib/array-0.1.0.0 -L/usr/local/lib/ghc-6.8.3/lib/process-1.0.0.1 -L/usr/local/lib/ghc-6.8.3/lib/unix-2.3.0.1 -L/usr/local/lib/ghc-6.8.3/lib/random-1.0.0.0 -L/usr/local/lib/ghc-6.8.3/lib/directory-1.0.0.1 -L/usr/local/lib/ghc-6.8.3/lib/filepath-1.1.0.0 -L/usr/local/lib/ghc-6.8.3/lib/old-time-1.0.0.0 -L/usr/local/lib/ghc-6.8.3/lib/old-locale-1.0.0.0 -L/usr/local/lib/ghc-6.8.3/lib/base-3.0.2.0 -L/usr/local/lib/ghc-6.8.3 -lHShaskell98-1.0.1.0 -lHSarray-0.1.0.0 -lHSprocess-1.0.0.1 -lHSunix-2.3.0.1 -lutil -ldl -lHSrandom-1.0.0.0 -lHSdirectory-1.0.0.1 -lHSfilepath-1.1.0.0 -lHSold-time-1.0.0.0 -lHSold-locale-1.0.0.0 -lHSbase-3.0.2.0 -lHSrts -lm -lgmp -ldl -lrt -u base_GHCziBase_Izh_static_info -u base_GHCziBase_Czh_static_info -u base_GHCziFloat_Fzh_static_info -u base_GHCziFloat_Dzh_static_info -u base_GHCziPtr_Ptr_static_info -u base_GHCziWord_Wzh_static_info -u base_GHCziInt_I8zh_static_info -u base_GHCziInt_I16zh_static_info -u base_GHCziInt_I32zh_static_info -u base_GHCziInt_I64zh_static_info -u base_GHCziWord_W8zh_static_info -u base_GHCziWord_W16zh_static_info -u base_GHCziWord_W32zh_static_info -u base_GHCziWord_W64zh_static_info -u base_GHCziStable_StablePtr_static_info -u base_GHCziBase_Izh_con_info -u base_GHCziBase_Czh_con_info -u base_GHCziFloat_Fzh_con_info -u base_GHCziFloat_Dzh_con_info -u base_GHCziPtr_Ptr_con_info -u base_GHCziPtr_FunPtr_con_info -u base_GHCziStable_StablePtr_con_info -u base_GHCziBase_False_closure -u base_GHCziBase_True_closure -u base_GHCziPack_unpackCString_closure -u base_GHCziIOBase_stackOverflow_closure -u base_GHCziIOBase_heapOverflow_closure -u base_GHCziIOBase_NonTermination_closure -u base_GHCziIOBase_BlockedOnDeadMVar_closure -u base_GHCziIOBase_BlockedIndefinitely_closure -u base_GHCziIOBase_Deadlock_closure -u base_GHCziIOBase_NestedAtomically_closure -u base_GHCziWeak_runFinalizzerBatch_closure -u base_GHCziConc_ensureIOManagerIsRunning_closure Using built-in specs. Target: i486-linux-gnu Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.1.3 --program-suffix=-4.1 --enable-__cxa_atexit --enable-clocale=gnu --enable-libstdcxx-debug --enable-mpfr --enable-checking=release i486-linux-gnu Thread model: posix gcc version 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2) /usr/lib/gcc/i486-linux-gnu/4.1.3/collect2 --eh-frame-hdr -m elf_i386 --hash-style=both -dynamic-linker /lib/ld-linux.so.2 -o a.out -u base_GHCziBase_Izh_static_info -u base_GHCziBase_Czh_static_info -u base_GHCziFloat_Fzh_static_info -u base_GHCziFloat_Dzh_static_info -u base_GHCziPtr_Ptr_static_info -u base_GHCziWord_Wzh_static_info -u base_GHCziInt_I8zh_static_info -u base_GHCziInt_I16zh_static_info -u base_GHCziInt_I32zh_static_info -u base_GHCziInt_I64zh_static_info -u base_GHCziWord_W8zh_static_info -u base_GHCziWord_W16zh_static_info -u base_GHCziWord_W32zh_static_info -u base_GHCziWord_W64zh_static_info -u base_GHCziStable_StablePtr_static_info -u base_GHCziBase_Izh_con_info -u base_GHCziBase_Czh_con_info -u base_GHCziFloat_Fzh_con_info -u base_GHCziFloat_Dzh_con_info -u base_GHCziPtr_Ptr_con_info -u base_GHCziPtr_FunPtr_con_info -u base_GHCziStable_StablePtr_con_info -u base_GHCziBase_False_closure -u base_GHCziBase_True_closure -u base_GHCziPack_unpackCString_closure -u base_GHCziIOBase_stackOverflow_closure -u base_GHCziIOBase_heapOverflow_closure -u base_GHCziIOBase_NonTermination_closure -u base_GHCziIOBase_BlockedOnDeadMVar_closure -u base_GHCziIOBase_BlockedIndefinitely_closure -u base_GHCziIOBase_Deadlock_closure -u base_GHCziIOBase_NestedAtomically_closure -u base_GHCziWeak_runFinalizzerBatch_closure -u base_GHCziConc_ensureIOManagerIsRunning_closure /usr/lib/gcc/i486-linux-gnu/4.1.3/../../../../lib/crt1.o /usr/lib/gcc/i486-linux-gnu/4.1.3/../../../../lib/crti.o /usr/lib/gcc/i486-linux-gnu/4.1.3/crtbegin.o -L/usr/local/lib/ghc-6.8.3/lib/haskell98-1.0.1.0 -L/usr/local/lib/ghc-6.8.3/lib/array-0.1.0.0 -L/usr/local/lib/ghc-6.8.3/lib/process-1.0.0.1 -L/usr/local/lib/ghc-6.8.3/lib/unix-2.3.0.1 -L/usr/local/lib/ghc-6.8.3/lib/random-1.0.0.0 -L/usr/local/lib/ghc-6.8.3/lib/directory-1.0.0.1 -L/usr/local/lib/ghc-6.8.3/lib/filepath-1.1.0.0 -L/usr/local/lib/ghc-6.8.3/lib/old-time-1.0.0.0 -L/usr/local/lib/ghc-6.8.3/lib/old-locale-1.0.0.0 -L/usr/local/lib/ghc-6.8.3/lib/base-3.0.2.0 -L/usr/local/lib/ghc-6.8.3 -L/usr/lib/gcc/i486-linux-gnu/4.1.3 -L/usr/lib/gcc/i486-linux-gnu/4.1.3 -L/usr/lib/gcc/i486-linux-gnu/4.1.3/../../../../lib -L/lib/../lib -L/usr/lib/../lib byteindex.o -lHShaskell98-1.0.1.0 -lHSarray-0.1.0.0 -lHSprocess-1.0.0.1 -lHSunix-2.3.0.1 -lutil -ldl -lHSrandom-1.0.0.0 -lHSdirectory-1.0.0.1 -lHSfilepath-1.1.0.0 -lHSold-time-1.0.0.0 -lHSold-locale-1.0.0.0 -lHSbase-3.0.2.0 -lHSrts -lm -lgmp -ldl -lrt -lgcc --as-needed -lgcc_s --no-as-needed -lc -lgcc --as-needed -lgcc_s --no-as-needed /usr/lib/gcc/i486-linux-gnu/4.1.3/crtend.o /usr/lib/gcc/i486-linux-gnu/4.1.3/../../../../lib/crtn.o byteindex.o: In function `sKE_info': (.text+0x8bf): undefined reference to `__stginit_utf8zmstringzm0zi3zi3_SystemziIOziUTF8_' collect2: ld returned 1 exit status *** Deleting temp files: Deleting: /tmp/ghc6586_0/ghc6586_0.s Warning: deleting non-existent /tmp/ghc6586_0/ghc6586_0.s *** Deleting temp dirs: Deleting: /tmp/ghc6586_0 Any help would be greatly appreciated. -- Ben George blgeorge(a)fastmail.fm -- http://www.fastmail.fm - The way an email service should be

2 1

bug in time libs?
by Jason Dusek 01 Dec '08

01 Dec '08

I'm on 6.10.1, using the libs provided with the binary of GHC for Mac OS X. I was fooling around with the time package in GHCi and something seems to be off. I have included a transcript. If I take a time diff, then the seconds are positive when the picos are negative and vice versa. -- _jsn |...transcript...| Prelude System.Time> :m + System.Time Prelude System.Time> t0 <- System.Time.getClockTime Prelude System.Time> t1 <- System.Time.getClockTime Prelude System.Time> diffClockTimes t0 t1 TimeDiff { tdYear = 0 , tdMonth = 0 , tdDay = 0 , tdHour = 0 , tdMin = 0 , tdSec = -7 , tdPicosec = 238846000000 } Prelude System.Time> diffClockTimes t1 t0 TimeDiff { tdYear = 0 , tdMonth = 0 , tdDay = 0 , tdHour = 0 , tdMin = 0 , tdSec = 7 , tdPicosec = -238846000000 }

2 1

Re: Binary Trees missing on hackage
by Andrew Wagner 01 Dec '08

01 Dec '08

The reasons I've always heard for this is that 1.) It's so easy to define a tree and 2.) There are tons of different variations of trees and what you can do with them. Not that I 100% agree, just what I've always heard. On Mon, Dec 1, 2008 at 6:09 AM, Christian Maeder <Christian.Maeder(a)dfki.de>wrote: > Hi, > > I was surprised that I could not find a "classical" binary tree data > structure on hackage, mainly for teaching purposes, like: > > data BinTree a = Nil | Node (BinTree a) a (BinTree a) > > with a couple of utility functions and instances (i.e. in-order traversal). > > Surely, one may argue, that such a tree can always be defined on the fly > when needed, but nobody would argue so for lists or tuples. (Although > I've rarely seen someone redefining lists, it is quite common to > introduce user-defined products or enumerations.) > > There are rose trees in Data.Tree and many other variants of trees are > conceivable, ie. > > data Boom a = Leaf a | Node (Boom a) (Boom a) > > or a kind of combination: > > data BinLeafTree a b = > Leaf b > | Node (BinLeafTree a b) a (BinLeafTree a b) > > I don't know, why I find the above BinTree most important. I'm not even > sure if such a tree could be re-used for Search- or AVL-trees that need > strict fields with redundant size or height counters for efficiency > reasons. > > In any case I would find such a data type at least as useful as > http://hackage.haskell.org/cgi-bin/hackage-scripts/package/OneTuple > > Who would supply and maintain such a package? Or did I simply not search > hard enough? > > Cheers Christian > > P.S. I took the (non-empty) "Boom" from the Boom-Hierarchy described in > "An Exploration of the Bird-Meertens Formalism" by Roland Backhouse > 1988, Groningen > > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries >

3 3

Can anybody give me some advice on this?
by Georgel Calin 01 Dec '08

01 Dec '08

Hello everybody, I have a piece of code that gives me headaches for some time now. Simply put, I would like to know which is the best way to overpass a "Couldn't match expected type * against inferred type *"-error and an "Occurs check: cannot construct the infinite type:"-error in the following situation: {-# OPTIONS -fglasgow-exts #-} > module Simple where > import Text.ParserCombinators.Parsec > > data HData a = O | C a deriving (Eq,Ord,Show) > data IN l = IN Int (HData l) deriving (Eq,Ord,Show) > data CH l = CH Char (HData l) deriving (Eq,Ord,Show) > -- data type is well-defined: > sample = C(IN 0 (C(CH 'a' (C(IN 1 (C(CH 'b' (C(IN 2 O))))))))) > > embeddedParser types = do string "end"; spaces; return O > {- > <|> do let h = head types > let t = tail types > case h of > 1 -> do aux <- pInt > rest <- embeddedParser $t++[h] > return $ C (IN aux rest) > 2 -> do aux <- pCh > rest <- embeddedParser $t++[h] > return $ C (CH aux rest) > _ -> error "unallowed type" > -} > pInt = do n <- fmap read $ many1 digit; return $ fromInteger n > pCh = do c <- letter; return $ c > simple = embeddedParser [1,2] > > -- the above result from sample I would like to get by running > -- parseTest simple "0a1b2end" > The way I see it, the defined datatype works but I am a bit clueless about how to modify the parser to accept things of the type (e.g.): HData (IN (CH (IN (CH (IN a))))) (and in general of any finite type embedded like this). Thanks in advance for your help, George

2 2