- Beginners - Haskell.org

Missing termination rule for recursive function
by Oscar Benjamin 05 Nov '12

05 Nov '12

Hi all, I'm new to this list and I'm in the very early stages of learning Haskell but I am confident with Python and some other languages. Seeing the connection between Haskell's lists and Python's generators I tried to reimplement a generator-based Python program in Haskell. I now have it working but I was hoping that someone could help me resolve a few queries. The Python program used itertools.permutations which is an iterator that yields all permutations of a sequence. Does Haskell have a similar function in it's standard library? I found a suggestion [1] for implementing a permutations function: -- Select each item and remainder from a sequence selections :: [a] -> [(a, [a])] selections [] = [] selections (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ] -- Permutations of a sequence permutations :: [a] -> [[a]] permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations ys ] After a while I established that this permutations function seemed to be returning an empty list. Looking at it I thought that it might be missing a termination condition so I added permutations [] = [] but the result was unchanged. When I changed it to permutations [] = [[]] I got the desired result. I can understand why this termination condition is needed to make the function recurse properly. What's confusing me though is why neither of the first two raised any kind of error at compile- or run-time. I would understand if an infinite loop had occurred (a common result for non-terminating recursion) but as far as I can tell it just returned an empty list. Can anyone explain to me how the function terminates in the three different cases? Also what is a good way of debugging this kind of problem? I found it quite difficult to establish that permutations was returning an empty list (in context there were other functions that could have been failing). Thanks in advance, Oscar [1] http://www.haskell.org/pipermail/haskell-cafe/2002-June/003122.html

3 5

cascade of if statements
by Emmanuel Touzery 05 Nov '12

05 Nov '12

Hello, I am wondering if this code can be made a bit nicer? I am checking if a file exists... and then if it exists I'm checking whether it's older than two hours from now. It is a bit annoying to have that second block in the else (i could make a second function but i think it all belongs in this function). This structure makes me think about the Maybe monad, where it would automatically exit after it would find out that the file doesn't exists, instead of having a cascade of if statements inside one another. But this function is already in the IO monad (maybe I'm thinking about this in the wrong way though). Any idea for an improvement? -- don't re-fetch if I fetched in the last 2 hours needToFetchAgain :: FilePath -> IO Bool needToFetchAgain export_filename = do exists <- doesFileExist export_filename if (not exists) then return False else do modif <- getModificationTime export_filename curTime <- getClockTime let diff = diffClockTimes curTime modif return $ tdSec diff >= (3600*2) -- 2 hours Thank you! Emmanuel

6 12

Double usage of a wire (arrow)
by Nathan Hüsken 05 Nov '12

05 Nov '12

Hey, If I double use an arrow (in this example a wire from netwire) like this: objectWire :: WireP [Collision] Object objectWire = (Object <$> integral_ initPos) . speedWire <*> speedWire will it be double evaluated, or can the compiler optimize this to evaluate speedWire only once? Thanks! Nathan

2 1

netwire, <<loop>> with accum1
by Nathan Hüsken 04 Nov '12

04 Nov '12

Hey, I have another <<loop>> with netwire. This is the minimal example I got it down to: {-# LANGUAGE Arrows #-} import Control.Wire mainWire :: WireP () Double mainWire = proc _ -> do rec out <- accum1 (+) 0 -< oldOut oldOut <- delay 0 -< out returnA -< out main = wireLoop mainWire wireLoop :: WireP () Double -> IO () wireLoop w' = do let (mx, w) = stepWireP w' 1.0 () putStrLn $ show mx wireLoop w Output: <<loop>> I am aware, in this context I could just use accum. I triggered the error where I changed integral_ and accum1. By the way, is it apropriate, that I always write these "netwire bug reports" over this list? Regards, Nathan

2 1

Excellent illustration of using the Haskell types -- revising Richard Bird's floor function so that it works properly
by Costello, Roger L. 04 Nov '12

04 Nov '12

Hi Folks, On page 82 of the book "Introduction to Functional Programming using Haskell" the author Richard Bird provides this sample implementation of the floor function: floor x = searchFrom 0 where searchFrom = decrease . upper . lower lower = until (<=x) decrease upper = until (>x) increase decrease n = n - 1 increase n = n + 1 The problem with that implementation is that it does not return an Integer value; rather, it returns a decimal (Double) value. Here's an example: floor (-3.4) -- returns (-4.0) That is wrong. The specification for floor says that it "maps a value of type Float to a value of type Integer." Clearly it is not producing an Integer result. I will now explain how to revise floor so that it returns an Integer value. In the process we will see an excellent illustration of the Haskell types. The heart of the problem is with the until function. Here is how Richard Bird implements it: until :: (a -> Bool) -> (a -> a) -> a -> a until p f y = if p y then y else until p f (f y) It takes three arguments, p, f, and y. Look at the signature of that function. The type of the third argument, y, dictates the type of the other arguments and the type of the result--whatever type y is, the other arguments must be the same type and the result must be the same type. Function until is first invoked by function lower: lower = until (<=x) decrease 0 Here are the three arguments provided to function until: (1) p is the partial function (<=x), where x is the input to the floor function. Suppose x is this value: x = (-3.4) (2) f is the function decrease (3) y is 0 Now you may argue, "Hey, the third argument, y, is 0 and that's an Integer, so clearly the result of function until will be an Integer." However, that is not correct. The type of 0 is ambiguous, it could be an Integer or it could be a Double. This ambiguity can be seen by checking its type using WinGHCi: :type 0 0 :: Num a => a The class Num is high up in Haskell's type hierarchy and it represents any number (Integer, Double, etc.). Thus, we cannot determine the type of function until's result just by examining its third argument. The other arguments will determine whether the 0 is an Integer or a Double. Let's examine the first argument: p is the partial function (<=x), where x = (-3.4) p compares "some value" against (-3.4). Let's check the type of (-3.4) using WinGHCi: :type (-3.4) (-3.4) :: Fractional a => a The datatype Double falls within the class Fractional. So p compares "some value" against a Double. Fundamental rule of Haskell: you cannot compare an Integer against a Double, you can only compare a Double against a Double. Recall that p compares "some value" against (-3.4). What is that "some value"? If we examine the body of function until we see that it is the third argument, y, and we know that y = 0. Ah, now we know how Haskell will treat 0: since the 0 is being compared against a Double value Haskell will treat the 0 as a Double. Okay, now that we know the type of y we can plug it into the type signature for function until: until :: (a -> Bool) -> (a -> a) -> Double -> a All a's must be of the same type, so the other a's must also be Double: until :: (Double -> Bool) -> (Double -> Double) -> Double -> Double Therefore function until will return a Double value. For example: until (<=x) decrease 0 -- returns (0.0) The output of function until is assigned to function lower: lower = until (<=x) decrease So the result of function lower is a Double value. The output of lower is then input to upper and the Double datatype propagates through the entire chain of composed functions: decrease . upper . lower The result of function floor is therefore a Double value. Okay, so how do we get floor to return an Integer value? The key is to prevent p in function until from casting the type of y to a Double. Recall function lower: lower = until (<=x) decrease 0 Notice that p is this partial function: (<=x) We must modify p to express, "Hey, compare x against an Integer value that has been cast to a Double value." That is implemented using a Lambda (anonymous) function: (\a -> (realToFrac a) <= x) Read that as: For whatever value, a, is provided convert it to a Fractional (Double) value and then compare it to x. Wow! So we are telling Haskell that the 0 is not to be treated as a Fractional (Double) value, it is to be treated as a Real (Integer) value. At last, we can implement function floor and it will return the desired Integer result: floor x = searchFrom 0 where searchFrom = decrease . upper . lower lower = until (\a -> (realToFrac a) <= x) decrease upper = until (\a -> (realToFrac a) > x) increase decrease n = n - 1 increase n = n + 1 Notice that wherever function until is called (in lower and upper), the first argument, p, is a Lambda (anonymous) function that takes its argument, a, and casts it from a Real (Integer) value to a Fractional (Double) value. Here are a couple examples of using this revised floor function: floor (-3.4) -- returns (-4) floor 3.4 -- returns 3 Notice that floor now returns an Integer value, which is what we want. Here is the signature for floor: floor :: (Fractional a, Ord a, Real c) => a -> c Read as: Invoke function floor with a Fractional (Double) value and it will return a Real (Integer) value. On page 83 Richard Bird shows a second version of function floor that uses a binary search: floor x = searchFrom (-1, 1) where searchFrom = fst . middle . cross(lower, upper) lower = until (<= x) double upper = until (> x) double middle = until done improve done (m, n) = (m + 1 == n) improve (m, n) = if p <= x then (p, n) else (m, p) where p = (m + n) div 2 That has multiple problems. First, it is syntactically not a well-formed Haskell program because the div operator (on the last line) must have back ticks ( ` ) surrounding it: where p = (m + n) `div` 2 Second, the functions lower and upper invoke function until. The first argument to until must be a Lambda function as described above: lower = until (\m -> (realToFrac m) <= x) double upper = until (\n -> (realToFrac n) > x) double Third, the function improve compares p (an Integer) against x (a Double), so p must be cast to a Fractional (Double) value: improve (m, n) = if (realToFrac p) <= x then (p, n) else (m, p) where p = (m + n) div 2 With those three changes the function works as desired: floor x = searchFrom (-1, 1) where searchFrom = fst . middle . cross(lower, upper) lower = until (\m -> (realToFrac m) <= x) double upper = until (\n -> (realToFrac n) > x) double middle = until done improve done (m, n) = (m + 1 == n) improve (m, n) = if (realToFrac p) <= x then (p, n) else (m, p) where p = (m + n) `div` 2 Here are a couple examples of using the revised floor function: floor (-3.4) -- returns (-4) floor 3.4 -- returns 3 Notice that floor now returns an Integer value, which is what we want. Here is the signature for floor: floor :: (Fractional a, Ord a, Real c) => a -> c Read as: Invoke function floor with a Fractional (Double) value and it will return a Real (Integer) value. /Roger

4 4

netwire accum delayed by one
by Nathan Hüsken 04 Nov '12

04 Nov '12

Hey, With this netwire based program: {-# LANGUAGE Arrows #-} import Control.Wire import Data.List mainWire :: WireP () Double mainWire = proc _ -> do accum (+) 0 -< 1 main = do wireLoop mainWire wireLoop :: WireP () Double -> IO () wireLoop w' = do let (mx, w) = stepWireP w' 1.0 () case mx of Left x -> putStrLn $ show mx Right x -> putStrLn $ show mx wireLoop w I get (output): Right 0.0 Right 1.0 Right 2.0 ... Should the output not start with 1.0 (and not 0.0)? The accum should be applied already in the first invocation, should it not? Regards, Nathan

2 5

best way to proceed with package install
by Michael Litchard 02 Nov '12

02 Nov '12

I am trying to install updated version of yesod-platform, and got this output from "cabal install yesod-platform". Could someone please advise on the most efficient way to proceed? SHA-1.5.1 (new version) asn1-data-0.7.1 (new version) base-unicode-symbols-0.2.2.4 (new version) base64-bytestring-1.0.0.0 (new version) blaze-markup-0.5.1.1 (new version) blaze-html-0.5.1.0 (new version) cipher-aes-0.1.2 (new package) data-default-0.5.0 (new version) cookie-0.4.0.1 (new version) date-cache-0.3.0 (new package) file-embed-0.0.4.6 (new version) hashable-1.1.2.5 (new version) case-insensitive-0.4.0.3 (new version) hspec-expectations-0.3.0.2 (new package) hspec-1.3.0.1 (new version) ... many more, snipping ... my concern was the next part of the message cabal: The following packages are likely to be broken by the reinstalls: yesod-platform-1.0.5 tls-extra-0.4.6 http-conduit-1.4.1.10 yesod-auth-1.0.2.1 yesod-1.0.1.6 authenticate-1.2.1.1 certificate-1.2.3 tls-0.9.5 yesod-core-1.0.1.2 yesod-static-1.0.0.3 yesod-persistent-1.0.0.1 yesod-form-1.0.0.4 yesod-json-1.0.0.1 yesod-default-1.0.1.1 skein-0.1.0.7 clientsession-0.7.5 pureMD5-2.1.0.3 wai-app-static-1.2.0.4 pwstore-fast-2.2 cprng-aes-0.2.3 crypto-conduit-0.3.2 yaml-0.7.0.3 persistent-template-0.9.0.2 persistent-sqlite-0.9.0.2 persistent-0.9.0.4 yesod-test-0.2.1 Use --force-reinstalls if you want to install anyway.

3 4

Netwire loop
by Nathan Hüsken 01 Nov '12

01 Nov '12

Hi, When testing this netwire sample program {-# LANGUAGE Arrows #-} import Control.Wire mainWire :: WireP () Double mainWire = proc i -> do rec value <- integral_ 0.0 -< oldValue oldValue <- delay 1.0 -< value returnA -< value main = do wireLoop mainWire wireLoop :: WireP () Double -> IO () wireLoop w' = do let (mx, w) = stepWireP w' 1.0 () case mx of Left ex -> putStrLn $ "Inhibited:" ++ (show ex) Right x -> putStrLn $ "Produced:" ++ (show x) wireLoop w I get this output: NetwireTest: <<loop>> But there should be not infinite loop, should there? Regards, Nathan

2 1

Algebraic types, shared parameters, pattern matching
by Christopher Howard 01 Nov '12

01 Nov '12

I noticed that with algebraic types I can do something like so: code -------- data Projectile = Bullet { range :: Double } | Missile { range :: Double } | Torpedo { range :: Double } f p = let r = range p in ...whatever... -------- (This is interesting in and of itself, as I don't in this case have to do pattern matching for each constructor. Also, apparently not all the constructors actually need to have a "range" selector for the program to compile!) However, what if I wanted to make the same function f (again, without multiple lines of pattern matching) but using a "simpler" data type like so: code: -------- type Range = Double data Projectile = Bullet Range | Missile Range | Torpedo Range -------- My first try was code -------- f (_ r) = ... -------- But that doesn't work. -- frigidcode.com indicium.us

2 1

firering event in netwire
by Nathan Hüsken 29 Oct '12

29 Oct '12

Hey, I have a few question about the usage of netwire: How do I fire events? For example my main wire should take keyboard events as input and output some state (which is than somehow outputed). I see that there is an event type, which has the some type as the identiy wire. I am just not sure how to use it? Or asked differently, how is the "keyDown" event defined, that was talked of in an earlier mail? Thanks! Nathan

2 11