- Haskell-Cafe - Haskell.org

are some of these "reverse" algos better than others? is there a quick and dirty way to reveal this fact?
by Thomas Hartman 23 Sep '07

23 Sep '07

I came up with the following functions to do "reverse." The first one is obviously bad, because of the expensive list concat. The last one, "myreverse", I think is the reference implementation you get in the prelude. The ones between, I'm not so sure. I suspect they're "naive" as the name indicates, but in practice they stop working at the same place as myreverse, at least on hugs. If versions "naive 2-5" are indeed inferior to myreverse, is there a quick and dirty way to reveal which ones are better via a profiling tool, or some trick like that? Something easier than doing the space/time complexity analysis by hand I mean? By the way, on ghc they all work out to [1..1000000] and beyond. -- fails on [1..100000] on win/hugs naivereverse [] = [] naivereverse (x:xs) = naivereverse xs ++ [x] -- fails on [1..1000000] on win/hugs naivereverse2 [] = [] naivereverse2 (x:xs) = ( last xs ) : ( naivereverse2 ( init xs ) ++ [x] ) naivereverse3 [] = [] naivereverse3 ( x : xs ) = ( last xs ) : naivereverse3 ( init xs ) naivereverse4 xs = myreverse' [] xs where myreverse' reversed [] = reversed myreverse' reversed xs = myreverse' ( (head xs) : reversed ) ( tail xs ) naivereverse5 xs = myreverse' [] xs where myreverse' reversed [] = reversed myreverse' reversed (x:xs) = myreverse' ( x : reversed ) xs -- this is the usual implementation right? myreverse xs = foldl f [] xs where f accum el = el : accum t.

5 5

Composition Operator
by PR Stanley 22 Sep '07

22 Sep '07

Hi (.) :: (b -> c) -> (a -> b) -> (a -> c) While I understand the purpose and the semantics of the (.) operator I'm not sure about the above definition. Is the definition interpreted sequentially - (.) is a fun taht takes a fun of type (b -> c) and returns another fun of type (a -> b) etc? Any ideas? Thanks, Paul

5 5

Win32 Open GL / Glut Applications
by John Wicket 21 Sep '07

21 Sep '07

I can take any of these opengl applications or other examples on the web, but I can't get the application to run on Win32? They will compile(except for the GLU ones) but when I launch them, the windows just closes? Is HOpenGL supported well on Win32? http://www.haskell.org/HOpenGL/ I have ghc 6.6

5 4

Sequencing Operations in a Monad
by SevenThunders 21 Sep '07

21 Sep '07

I have a matrix library written in C and interfaced into Haskell with a lot of additional Haskell support. The C library of course has a lot of side effects and actually ties into the BLAS libraries, thus at the present time, most of the interesting calls are done in the IO monad. I have no intention of rewriting what I've done so far or using someone elses Matrix library. (Mine is tuned somewhat for my application). I attempted to extend my Haskell matrix interface using type classes (real and complex matrices) and have run into a conceptual problem. I would like to be able to use operator notation for matrix arithmetic. e.g. R = Q * (A + B) Unfortunately if I wrap my matrix references in the IO monad, then at best computations like S = A + B are themselves IO computations and thus whenever they are 'invoked' the computation ends up getting performed repeatedly contrary to my intentions. For example I might have some code like this, let S = A += B in do (r,c) <- size S k <- matindex S ..... code of this nature results in S being applied twice and if the operator += has side effects, those side effects will be applied twice. Even if there are no side effects the computation will unnecessarily be applied twice. What I need is a way to force a single execution of the IO action without losing the syntax sugar. If you arrange the types to try to do all the operations inside the IO monad you can't chain together more than 1 binary operation. eg. do S <- A + B Z <- Q * S vs do S <- Q * (A + B) Are there any suggestions for this dilemma? Am I using the wrong monad for this task? -- View this message in context: http://www.nabble.com/Sequencing-Operations-in-a-Monad-tf4446047.html#a1268… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

6 10

Re: [Haskell-cafe] reverse with foldl
by Miguel Mitrofanov 21 Sep '07

21 Sep '07

> reverse = foldl (\x -> \xs -> xs:x) [] Doesn't typecheck.

2 1

Interesting folds over bytestring lists?
by Justin Bailey 21 Sep '07

21 Sep '07

I have a data structure which is a list of bytestrings, but externally it looks like one big string. One of the operations I want to support takes a section of the string, starting at some arbitrary index and ending somewhere further down the line. In implementing the function I came up with the two functions below, dropTo and takeTo. In my mind, dropTo moves over the list of bytestrings until it reaches the starting point, and then returns the rest. takeTo, in contrast, scans over the list until it has seen enough bytes to return the amount requested. In both cases I am trying to share structure as much as possible in order to avoid unnecessary copying and space leaks. I thought these two functions were interested and am looking for feedback, comments, improvements, etc. Thanks! import qualified Data.ByteString as S import qualified Data.ByteString.Lazy as L import qualified Data.ByteString.Base as B import Test.QuickCheck import Data.List (foldl') import Data.Word dropTo :: Int -> [L.ByteString] -> [L.ByteString] dropTo _ [] = [] dropTo amt strs = let dropTo' :: (Int, [L.ByteString]) -> L.ByteString -> (Int, [L.ByteString]) dropTo' (rem, acc) ss | rem == 0 = (0, acc) | otherwise = let chunks = L.toChunks ss in case foldl' dropStricts (rem, chunks) chunks of (!n, rest) | null rest -> (n, drop 1 acc) | otherwise -> (0, L.fromChunks rest : drop 1 acc) dropStricts :: (Int, [S.ByteString]) -> S.ByteString -> (Int, [S.ByteString]) dropStricts (rem, acc) str | rem == 0 = (0, acc) | rem - S.length str == 0 = (0, drop 1 acc) | rem - S.length str < 0 = (0, S.drop rem str : (drop 1 acc)) | otherwise = (rem - S.length str, drop 1 acc) (_, rest) = foldl' dropTo' (amt, strs) strs in rest takeTo :: Int -> [L.ByteString] -> [L.ByteString] takeTo _ [] = [] takeTo amt strs = let countLazies :: (Int, Int, L.ByteString) -> L.ByteString -> (Int, Int, L.ByteString) countLazies (rem, !total, lazyLeftover) ss | rem == 0 = (0, total, lazyLeftover) | otherwise = let chunks = L.toChunks ss in case foldl' countStricts (rem, 0, S.empty) chunks of (!n, amt, strictLeftover) | S.null strictLeftover -> (n, total + 1, L.empty) | otherwise -> (n, total, L.fromChunks (take amt chunks ++ [strictLeftover])) countStricts :: (Int, Int, S.ByteString) -> S.ByteString -> (Int, Int, S.ByteString) countStricts (rem, !total, leftover) str | rem == 0 = (0, total, leftover) | rem - S.length str == 0 = (0, total + 1, S.empty) | rem - S.length str < 0 = (0, total, S.take rem str) | otherwise = (rem - S.length str, total + 1, S.empty) in case foldl' countLazies (amt, 0, L.empty) strs of (_, total, leftover) | L.null leftover -> take total strs | otherwise -> take total strs ++ [leftover] prop_dropToNonEmpty :: [[Word8]] -> Int -> Property prop_dropToNonEmpty strs amt = amt >= 0 && (all (not . null) strs) ==> all (not . L.null) (dropTo amt (map (L.pack) strs)) prop_dropToCorrect :: [[Word8]] -> Int -> Property prop_dropToCorrect strs amt = let lazyStr = L.drop amt64 (toLazyBS strs) amt64 = fromIntegral amt in amt >= 0 && (all (not . null) strs) ==> (L.concat (dropTo amt (map (L.pack) strs))) == lazyStr prop_takeToNonEmpty :: [[Word8]] -> Int -> Property prop_takeToNonEmpty strs amt = amt >= 0 && (all (not . null) strs) ==> all (not . L.null) (takeTo amt (map (L.pack) strs)) prop_takeToCorrect :: [[Word8]] -> Int -> Property prop_takeToCorrect strs amt = let lazyStr = L.take amt64 (toLazyBS strs) amt64 = fromIntegral amt in amt >= 0 && (all (not . null) strs) ==> (L.concat (takeTo amt (map (L.pack) strs))) == lazyStr -- Functions and instances for testing purposes toLazyBS :: [[Word8]] -> L.ByteString toLazyBS = L.concat . map L.pack instance Arbitrary Word8 where arbitrary = elements [minBound .. maxBound] coarbitrary = undefined main = do putStrLn "prop_takeToNonEmpty" quickCheck prop_takeToNonEmpty putStrLn "prop_takeToCorrect" quickCheck prop_takeToCorrect putStrLn "prop_dropToCorrect" quickCheck prop_dropToCorrect putStrLn "prop_dropToNonEmpty" quickCheck prop_dropToNonEmpty

4 5

Graphics.SOE
by Peter Padawitz 21 Sep '07

21 Sep '07

Can scrollbars be attached to windows created with openWindow?

1 0

Slightly Off-topic
by PR Stanley 21 Sep '07

21 Sep '07

Hi Does anyone know of a good active list for students and experts in discrete mathematics, in particular, logic? Thanks, Paul

1 0

Accumulator value for "and" and "or"
by PR Stanley 21 Sep '07

21 Sep '07

Hi or = foldl (||) False and = foldl (&&) True I can understand the rationale for the accumulator value - True && [] where [] = True and True || [] where [] = False Other than the practical convenience is there a reason for having the empty list in and and or equating to True and False? Thanks, Paul

4 3

How can I stop GHCi from calling "show" for IO actions?
by Ryan Ingram 21 Sep '07

21 Sep '07

Prelude> let inf = repeat 1 Prelude> inf [1,1,(lots of output until I press ctrl-c),Interrupted. (I expect this to happen) Prelude> let x = inf (no output here!) Prelude> :t x x :: [Integer] Prelude> return inf [1,1,(lots of output until I press ctrl-c),Interrupted. (I also expect this to happen) Prelude> y <- return inf [1,1,(lots of output until I press ctrl-c),Interrupted. (I do not expect this to happen here!) Prelude> :t y <interactive>:1:0: Not in scope: 'y' Is this a bug? Why does "y <- return exp" have different behavior than "let y = exp"? Is there a way to make GHCi not print the result of an action but still make my variables get bound? -- ryan

10 14