- Haskell-Cafe - Haskell.org

Substring replacements
by Branimir Maksimovic 24 Dec '05

24 Dec '05

I've finally performed test on amd64 and result is a same as on intel. KMP always wins. So KMP is best suited for non indexed strings and I guess should be used in library as prefered search/replace method. This test favors straightforward search. [bmaxa@devel64 myhaskell]$ time ./KMP Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m10.783s user 0m10.769s sys 0m0.016s [bmaxa@devel64 myhaskell]$ time ./straightforward Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m11.769s user 0m11.741s sys 0m0.028s [bmaxa@devel64 myhaskell]$ uname -a Linux devel64.office.kom 2.6.14-skas3-v8.2 #2 Fri Nov 11 21:19:36 CET 2005 x86_64 x86_64 x86_64 GNU/Linux Greetings, Bane. _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

3 8

Vectors in Haskell
by Jeff.Harper＠handheld.com 23 Dec '05

23 Dec '05

Dear Haskell, Most of the time we get along well. But, I'm growing weary of the arguments, fights, and nitpicking when I try to implement new mathematical types and overload your operators. I don't know how to cooperate with your type systems. At moments like this, I think about getting back together with C++. I love you. But, I also love implementing complex numbers, vectors, matrices, and quaternions, and Galois fields. C++ is not nearly as elegant and beautiful as you. But, C++ doesn't complain when I try to do this. Isn't there some way we can work things out so I can implement these types with you? Seriously, I'm trying to implement a vector. I'm starting with vector addition: {- This code is works with Glasgow, ghci, with these options: -fglasgow-exts -fallow-undecidable-instances -fno-monomorphism-restriction -fallow-incoherent-instances -} data Vector a = Vector [a] deriving Show class Add a b c | a b -> c where (.+) :: a -> b -> c instance Add Int Int Int where (.+) x y = x + y instance Add Int Double Double where (.+) x y = (fromIntegral x) + y instance Add Double Int Double where (.+) x y = x + (fromIntegral y) instance Add Double Double Double where (.+) x y = x + y instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) where (.+) (Vector x) (Vector y) = Vector (zipWith (.+) x y) vi1 = Vector [(1::Int)..3] vi2 = Vector [(10::Int),15,2] vd1 = Vector [(1::Double)..3] vd2 = Vector [(10::Double),15,2] test1 = vi1 .+ vi2 test2 = vi1 .+ vd2 test3 = vd1 .+ vi2 test4 = vd1 .+ vd2 v1 = Vector [1,2,3] v2 = Vector [10,15,2] However, it is necessary to explicitly nail down the type of the Vector. v1 and v2 are more general. *Main> :t v1 v1 :: forall a. (Num a) => Vector a *Main> :t v2 v2 :: forall a. (Num a) => Vector a *Main> test2 I'd like for .+ to work with v1 and v2. So, I can use things like Vector [1,2,3] in expressions, instead of Vector[(1::Int),2,3]. However, v1 and v2 do not work with .+ in the code I produced above. Does anyone have any ideas how to make this work? I hoped defining .+ more generally for instances of Num would make my vector addition code work with v1 and v2. My failed attempt involved making the following changes . . . -- I added this instance (Num d) => Add d d d where (.+) x y = x + y -- instance Add Int Int Int where -- (.+) x y = x + y instance Add Int Double Double where (.+) x y = (fromIntegral x) + y instance Add Double Int Double where (.+) x y = x + (fromIntegral y) -- instance Add Double Double Double where -- (.+) x y = x + y When I make these changes and compile, I get the following error messages on the declaration of test1 and test4. . . Vector2.hs:38:12: Overlapping instances for Add (Vector Int) (Vector Int) (Vector Int) arising from use of `.+' at Vector2.hs:38:12-13 Matching instances: Vector2.hs:31:0: instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) Vector2.hs:15:0: instance (Num d) => Add d d d In the definition of `test1': test1 = vi1 .+ vi2 Vector2.hs:41:12: Overlapping instances for Add (Vector Double) (Vector Double) (Vector Double) arising from use of `.+' at Vector2.hs:41:12-13 Matching instances: Vector2.hs:31:0: instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) Vector2.hs:15:0: instance (Num d) => Add d d d In the definition of `test4': test4 = vd1 .+ vd2 I interpret this as saying that the compiler doesn't know if the .+ in "test1 = vi1 .+ vi2" should match the Vector instance or the Num instance. I could understand this if Vector was an instance of class Num. However, this is not the case. I figure either Glasgow has a bug or I don't really understand the error message. I'd be grateful for any suggestions or pointers to information on how to implement vectors (or other mathematical types) so they seamlessly and intuitively work with types, classes and operators already built into Haskell. Or, if someone could point to a more intermediate level book on working with the Haskell type system, that would be great.

6 5

Arrows and pickler combinators
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, I'm trying to monadify the pickler code. sequ below positively looks like >>= but you can't really join both pickle and unpickle into a single monad. I would like to keep the ops together, though, as this allows me a single specification for both pickling and unpickling. Cale suggested that PU is really an arrow in that it supports both input and output. I could not find an example of such an arrow, though. I thought that it could be a "dual arrow" but then could not find a description for one. I would appreciate your suggestions! The original paper is at http:// research.microsoft.com/ ~akenn/fun/picklercombinators.pdf Thanks, Joel P.S. data PU a = PU { appP :: Ptr Word8 -> Int -> a -> IO Int, appU :: Ptr Word8 -> Int -> IO (a, Int), appS :: a -> IO Int } pickle :: PU a -> Ptr Word8 -> Int -> a -> IO Int pickle p ptr ix value = appP p ptr ix value unpickle :: PU a -> Ptr Word8 -> Int -> IO (a, Int) unpickle p ptr ix = appU p ptr ix sizeup :: PU a -> a -> IO Int sizeup p value = appS p value lift :: a -> PU a lift x = PU (\_ ix _ -> return ix) (\_ ix -> return (x, ix)) (\_ -> return 0) sequ :: (b -> a) -> PU a -> (a -> PU b) -> PU b sequ f pa k = PU (\ptr ix b -> do let a = f b pb = k a ix1 <- appP pa ptr ix a appP pb ptr ix1 b) (\ptr ix -> do (a, ix1) <- appU pa ptr ix let pb = k a appU pb ptr ix1) (\b -> do let a = f b pb = k a sz1 <- appS pa a sz2 <- appS pb b return $ sz1 + sz2) pair :: PU a -> PU b -> PU (a,b) pair pa pb = sequ fst pa (\ a -> sequ snd pb (\ b -> lift $! (a, b))) -- http://wagerlabs.com/

3 4

Arrows for invertible programming: Notation question
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, I have been looking at the code for the "Arrows for invertible programming" paper (http://www.cs.ru.nl/A.vanWeelden/bi-arrows/) and I have a question about syntax. ghci surely does not like it. What does this mean and how do I make it compile? mapl{|a, b|arr|} :: (mapl{|a, b|arr|}, ArrowChoice arr, BiArrow arr) => arr a b Thanks, Joel -- http://wagerlabs.com/

3 4

Battling time leaks
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, It looks like I successfully squashed my time leaks and moving my serialization to Ptr Word8 got me as close to the metal as possible. I'm still getting wierd results, though, and they look like a time leak. ORANGE ALERT: 0s, 6s, SrvServerInfo ORANGE ALERT: 0s, 8s, SrvServerInfo ORANGE ALERT: 0s, 9s, SrvServerInfo ORANGE ALERT: 0s, 9s, SrvServerInfo ORANGE ALERT: 0s, 7s, SrvServerInfo unstuff :: Ptr Word8 -> Int -> IO Command unstuff ptr ix = do TOD time1 _ <- getClockTime (kind, ix1) <- unpickle puCmdType ptr ix TOD time2 _ <- getClockTime (cmd', _) <- unpickle (puCommand kind) ptr ix1 TOD time3 _ <- getClockTime when (time3 - time1 > 3) $ -- fail here with the messages above I would like to know where the time is going but how do I troubleshoot something like this? My understanding is that regular profiling will give me the total time spent by cost-center so if I add cost-center annotations it will not give me the average time per run. Come to think about it, the profiling report gives me the # of entries and the total time so I can get the average. Any other suggestions on how to figure out what is going on here? Thanks, Joel -- http://wagerlabs.com/

2 4

Encapsulation in Haskell
by Creighton Hogg 23 Dec '05

23 Dec '05

Hi guys, So one of the big things in object oriented programming is encapsulation, and I'm wondering how to do it properly in Haskell. How do you define new data types but minimize the dependence of external packages on the exact nature of the data definition?

5 4

Type inference for infinite structures
by Matt Collins 23 Dec '05

23 Dec '05

Hi everyone, I'm relatively new to Haskell and was a bit troubled by the problem of assigning a type to infinite structures. To give a clear example, suppose we have data Nat = Zero | Succ Nat omega = Succ omega What type then does omega have? According to GHCi, omega :: Nat. But surely this can only be the case if we already have that omega :: Nat (on the right hand side of the equation)? I can see that the type assignment is valid, but is it necessarily the case? Does it not, somehow, sidestep the inductive base case of the definition of a Nat? Thanks, Matt

2 2

Statements spanning multiple lines?
by Daniel Carrera 23 Dec '05

23 Dec '05

Hi all, How do I write a statement that spans multiple lines? I have this function: pythagoras n = [(a,b,c) | a <-[1..n], b <-[1..n], c <-[1..n], a <= b, b < c, a*a + b*b == c*c] This should all be in one line. I know some ways to make the line shorter, like defining local functions and using 'filter'. But the code would be clearer if I could just make this one statement span several lines. Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

4 6

RE: GHC optimization issue
by Simon Peyton-Jones 23 Dec '05

23 Dec '05

(Brief because I'm at home.) Use INLINE (alone) to include swap at its call sites. (That gives perfect per-call-site specialisation.) Use SPECIALISE (alone) to make a specialised copy of swap, which is then not duplicated at each call site, but instead is called. No need to use them both. The fact that GHC inlines the (big) unspecialised version and not the (apparently smaller) specialised version, is something we should look into. Simon | -----Original Message----- | From: Joel Reymont [mailto:joelr1@gmail.com] | Sent: 22 December 2005 14:09 | To: Haskell-Cafe Cafe | Cc: Simon Peyton-Jones; Simon Marlow | Subject: GHC optimization issue | | Folks, | | I have been trying to improve my byte swapping routines as part of my | effort to speed up serialization. I then tried to look at the core | output from GHC to see what it was converting my code into. Brandon | (skew on #haskell) helped me code a TH version but then I went with a | regular CPP version instead. | | The point of contention is that the logical approach to optimization | does not produce expected results. The only difference between the | following two core outputs is the presence or absence of specialize | and inline pragmas. The code is the same. | | The version without pragmas inlines foo1 into | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) | of ww1_a2eo { __DEFAULT -> | case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of | ww_a2f4 { __DEFAULT -> | GHC.Word.W16# (GHC.Prim.narrow16Word# | (GHC.Prim.plusWord# ww1_a2eo ww_a2f4)) | } | } | | Whereas the version _with_ pragmas produces a function call: | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 Swap1.$w$sswap16 __word 3855 | of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | | Is there a reasonable explanation? | | Both versions compiled thusly: ghc --make Foo.hs -O -ddump-simpl > foo | | Swap: | | {-# OPTIONS_GHC -fglasgow-exts -cpp #-} | module Swap1 | ( | swap16 | ) | where | | import Data.Word | import Data.Int | import Data.Bits | | #define BIG_ENDIAN 1 | | {-# SPECIALIZE swap16 :: Word16 -> Word16 #-} | {-# SPECIALIZE swap16 :: Int16 -> Int16 #-} | {-# INLINE swap16 #-} | | swap16 :: Bits a => a -> a | #ifdef BIG_ENDIAN | swap16 v = (v `shiftR` 8) + ((v .&. 0xFF) `shiftL` 8) | #else | swap16 v = v | #endif | | Foo: | | module Main where | | import Data.Word | import Swap1 | | foo1 :: Word16 | foo1 = swap16 0x0f0f | | main = putStrLn $ show foo1 | | Core output for the version WITH pragmas, see the version w/o pragmas | way below | | ==================== Tidy Core Rules ==================== | "SPEC Swap1.swap16" __forall {$dBits_X1Co :: {Data.Bits.Bits | GHC.Int.Int16}} | Swap1.swap16 @ GHC.Int.Int16 $dBits_X1Co | = Swap1.$sswap16 ; | "SPEC Swap1.swap16" __forall {$dBits_X1Cv :: {Data.Bits.Bits | GHC.Word.Word16}} | Swap1.swap16 @ GHC.Word.Word16 $dBits_X1Cv | = Swap1.$sswap161 ; | | | ==================== Tidy Core ==================== | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 Swap1.$w$sswap16 __word 3855 | of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | | ==================== Tidy Core ==================== | Swap1.$w$sswap16 :: GHC.Prim.Word# -> GHC.Prim.Word# | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.$w$sswap16 = \ (ww_s1I5 :: GHC.Prim.Word#) -> | case GHC.Prim.Word# GHC.Word.$wshift3 ww_s1I5 | (-8) of ww1_a1Gx { __DEFAULT -> | case GHC.Prim.Word# GHC.Word.$wshift3 | (GHC.Prim.and# ww_s1I5 __word 255) 8 | of ww11_a1Hd { __DEFAULT -> | GHC.Prim.narrow16Word# (GHC.Prim.plusWord# | ww1_a1Gx ww11_a1Hd) | } | } | | Swap1.$w$sswap161 :: GHC.Prim.Int# -> GHC.Prim.Int# | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.$w$sswap161 = \ (ww_s1HV :: GHC.Prim.Int#) -> | case GHC.Prim.Int# GHC.Int.$wshift2 ww_s1HV | (-8) of ww1_a1Fk { __DEFAULT -> | case GHC.Prim.Int# GHC.Int.$wshift2 | (GHC.Prim.word2Int# | (GHC.Prim.and# (GHC.Prim.int2Word# ww_s1HV) __word 255)) | 8 | of ww11_a1G5 { __DEFAULT -> | GHC.Prim.narrow16Int# (GHC.Prim.+# ww1_a1Fk | ww11_a1G5) | } | } | | Swap1.$sswap16 :: GHC.Int.Int16 -> GHC.Int.Int16 | [GlobalId] | [Arity 1 | Worker Swap1.$w$sswap161 | NoCafRefs | Str: DmdType U(L)m] | Swap1.$sswap16 = __inline_me (\ (w_s1HT :: GHC.Int.Int16) -> | case GHC.Int.Int16 w_s1HT of w1_X1I5 | { GHC.Int.I16# ww_s1HV -> | case GHC.Int.Int16 Swap1.$w$sswap161 | ww_s1HV of ww1_s1I0 { __DEFAULT -> | GHC.Int.I16# ww1_s1I0 | } | }) | | Swap1.$sswap161 :: GHC.Word.Word16 -> GHC.Word.Word16 | [GlobalId] | [Arity 1 | Worker Swap1.$w$sswap16 | NoCafRefs | Str: DmdType U(L)m] | Swap1.$sswap161 = __inline_me (\ (w_s1I3 :: GHC.Word.Word16) -> | case GHC.Word.Word16 w_s1I3 of | w1_X1Ih { GHC.Word.W16# ww_s1I5 -> | case GHC.Word.Word16 Swap1.$w | $sswap16 ww_s1I5 of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | }) | | Swap1.swap16 :: forall a_a1aQ. (Data.Bits.Bits a_a1aQ) => a_a1aQ -> | a_a1aQ | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.swap16 = __inline_me (\ (@ a_a1dB) | ($dBits_a1ip :: {Data.Bits.Bits | a_a1dB}) -> | let { | $dNum_s1BO :: {GHC.Num.Num a_a1dB} | [Str: DmdType {a1ip->U | (SAAAAAAAAAAAAAAAAA)}] | $dNum_s1BO = Data.Bits.$p1Bits @ | a_a1dB $dBits_a1ip } in | let { | lit_s1BN :: a_a1dB | [Str: DmdType {a1ip->U | (SAAAAAAAAAAAAAAAAA) s1BO->U(AAAAAAAAS)}] | lit_s1BN = GHC.Num.fromInteger @ | a_a1dB $dNum_s1BO (GHC.Num.S# 255) | } in | \ (v_a1aW :: a_a1dB) -> | GHC.Num.+ | @ a_a1dB | $dNum_s1BO | (Data.Bits.shiftR @ a_a1dB | $dBits_a1ip v_a1aW (GHC.Base.I# 8)) | (Data.Bits.shiftL | @ a_a1dB | $dBits_a1ip | (Data.Bits..&. @ a_a1dB | $dBits_a1ip v_a1aW lit_s1BN) | (GHC.Base.I# 8))) | | | Core output without pragmas: | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) | of ww1_a2eo { __DEFAULT -> | case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of | ww_a2f4 { __DEFAULT -> | GHC.Word.W16# (GHC.Prim.narrow16Word# | (GHC.Prim.plusWord# ww1_a2eo ww_a2f4)) | } | } | | --- | Swap1.swap16 :: forall a_a1aQ. (Data.Bits.Bits a_a1aQ) => a_a1aQ -> | a_a1aQ | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.swap16 = \ (@ a_a1dB) ($dBits_a1ip :: {Data.Bits.Bits a_a1dB}) -> | let { | $dNum_s1BK :: {GHC.Num.Num a_a1dB} | [Str: DmdType] | $dNum_s1BK = case {GHC.Num.Num a_a1dB} $dBits_a1ip | of tpl_B1 { Data.Bits.:DBits tpl1_B2 | tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba | tpl10_Bb tpl11_Bc tpl12_Bd tpl13_Be tpl14_Bf tpl15_Bg tpl16_Bh | tpl17_Bi tpl18_Bj -> | tpl1_B2 | } } in | let { | lit_s1BM :: a_a1dB | [Str: DmdType] | lit_s1BM = case a_a1dB $dNum_s1BK | of tpl_B1 { GHC.Num.:DNum tpl1_B2 | tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba -> | tpl9_Ba Swap1.lvl1 | } | } in | \ (v_a1aW :: a_a1dB) -> | tpl3_B4 | (case a_a1dB $dBits_a1ip | of tpl10_Xy { Data.Bits.:DBits tpl11_XB | tpl12_XD tpl13_XF tpl14_XH tpl15_XJ tpl16_XL tpl17_XN tpl18_XP | tpl19_XR tpl20_Bb tpl21_Bc tpl22_Bd tpl23_Be tpl24_Bf tpl25_Bg | tpl26_Bh tpl27_Bi tpl28_Bj -> | tpl26_Bh v_a1aW Swap1.lvl | }) | (case a_a1dB $dBits_a1ip | of tpl10_Xy { Data.Bits.:DBits tpl11_XB | tpl12_XD tpl13_XF tpl14_XH tpl15_XJ tpl16_XL tpl17_XN tpl18_XP | tpl19_XR tpl20_Bb tpl21_Bc tpl22_Bd tpl23_Be tpl24_Bf tpl25_Bg | tpl26_Bh tpl27_Bi tpl28_Bj -> | tpl25_Bg (tpl12_XD v_a1aW lit_s1BM) Swap1.lvl | }) | | -- | http://wagerlabs.com/ | | | |

2 1

ANN: HDBC 0.6.0
by John Goerzen 23 Dec '05

23 Dec '05

Hello, Version 0.6.0 of HDBC and the Sqlite3 bindings are now available. New features since Tuesday's 0.5.0 announcement include: * New type system for marshalling different Haskell types back and forth * New support for querying meta-information about the server * Much improved documentation * Fix for a race condition in the Sqlite3 binding * New fetchAllRows function that returns a lazy list of result rows (think hGetContents for database queries) I will shortly begin work on a PostgreSQL binding. Also, I plan to write a MissingH interface module. The main idea of that is to provide a SQL backend for the MissingH AnyDBM interface (which uses *dbm databases for persistent hashes). Combined with Sqlite, this provides a very interesting and easy to use persistent hash interface. -- John

1 0