- Beginners - Haskell.org

web server availability
by Paul Higham 07 Jun '10

07 Jun '10

Is anyone else having trouble reaching the haskell.org web site? I have been unsuccessful in trying to reach it for over a week. Does anybody know what's going on? ::paul

2 1

Trying around with Functional Reactive Programming
by Nathan Huesken 07 Jun '10

07 Jun '10

Hi, I tried to read the article "Simple efficient functional reactivity". Being a beginner to haskell, I had my problems. I decided to try with around with some implementations first. I found this: http://conal.net/fran/ Unfortantlly it is windows only, I am on gentoo linux. Is there a linux compatible implementation I can experiment with? Thanks! Nathan

2 1

Fractal map generator in Haskell - can it be simplified?
by Maciej Piechotka 07 Jun '10

07 Jun '10

I tried to implement fractal map generator in Haskell. While the code is correct (I believe) it is not nice: > {-# LANGUAGE FlexibleContexts #-} > import Control.Applicative > import Data.Array > import Data.Bits > import Data.Foldable > import Data.Ix > import Data.Random > import Data.Traversable > import Debug.Trace > import Text.Printf > import Prelude hiding (sum) > > ctz :: Bits a => a -> Int > ctz x@0 = bitSize x > ctz x = let ctz' n | x .&. bit n /= 0 = n > | otherwise = ctz' (n+1) > in ctz' 0 > Count trailing zeros. > imLog :: Integral a => a -> a -> a > imLog b x | x | otherwise = doDiv (x`div`(b^l)) l > where l = 2 * imLog (b*b) x > doDiv x l | x | otherwise = doDiv (x`div`b) (l+1) > Integer logarithm (from Haskell report) > genArray :: Ix i => (i, i) -> (i -> a) -> Array i a > genArray r f = listArray r (map f (range r)) > Helper function (generate array using function taking index) > randArray :: Ix i => (i, i) -> RVar a -> RVar (Array i a) > randArray r v = listArray r <$> sequenceA (replicate (rangeSize r) v) > Generate array from random value generator. > sizeArray :: (Bits i, Ix (i, i), Ord i) => ((i, i), (i, i)) -> Array (i, i) i > sizeArray r = > genArray r (\(x, y) -> fromIntegral (min (findSize x) (findSize y))) > where findSize = fromIntegral . ctz > Generate array how far we should look from this point. > data FType = Box | Cross deriving (Eq, Show) > > ftypeArray :: (Bits i, Ix (i, i), Ord i, Integral i) => > (i, i) -> Array (i, i) FType > ftypeArray n = let arr = genArray ((0, 0), n) arrF > arrF (x, y) > | x == y = Box > | x == 0 || y == 0 = Cross > | x <= 2 && y <= 2 = Cross > | x > y = arr ! (x - 2^(imLog 2 x), y) > | x < y = arr ! (x, y - 2^(imLog 2 y)) > in arr > Generate array should we look on diagonals or columns/rows > fracArray :: (Bits i, Ix (i, i), Ord i, Fractional v, Integral i) > => i -> v -> RVar v -> RVar (Array (i, i) v) > fracArray n d v = do > let size = 2^n > ra <- randArray ((0, 0), (size - 1, size)) v > let s = sizeArray ((0, 0), (size, size)) > ft = ftypeArray (size, size) > arr = genArray ((0, 0), (size, size)) arrF > randF (x, y) = d*(ra ! (x, y))*2^(size - (s ! (x, y))) > average l = sum l / fromIntegral (length l) > arrF (x, y) > | x == 0 && y == 0 > = ra ! (0, 0) > | x == 0 && y == size > = ra ! (0, size) > | x == size > = arr ! (0, y) > | x == 0 > = randF (x, y) + average [arr ! (x, y - cs), > arr ! (x, y + cs), > arr ! (x + cs, x)] > | y == 0 > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y + cs)] > | y == size > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y - cs)] > | ft ! (x, y) == Cross > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y - cs), > arr ! (x, y + cs)] > | ft ! (x, y) == Box > = randF (x, y) + average [arr ! (x - cs, y - cs), > arr ! (x - cs, y + cs), > arr ! (x + cs, y - cs), > arr ! (x + cs, y + cs)] > where cs = 2 ^ (s ! (x, y)) > return arr > Any advice how to improve it? Regards PS. Am I correct that it has O(size^2) complexity i.e. O(2^n) [which is optimal]?

1 0

Fractal map generator in Haskell - can it be simplified?
by Maciej Piechotka 07 Jun '10

07 Jun '10

I tried to implement fractal map generator in Haskell. While the code is correct (I believe) it is not nice: > {-# LANGUAGE FlexibleContexts #-} > import Control.Applicative > import Data.Array > import Data.Bits > import Data.Foldable > import Data.Ix > import Data.Random > import Data.Traversable > import Debug.Trace > import Text.Printf > import Prelude hiding (sum) > > ctz :: Bits a => a -> Int > ctz x@0 = bitSize x > ctz x = let ctz' n | x .&. bit n /= 0 = n > | otherwise = ctz' (n+1) > in ctz' 0 > Count trailing zeros. > imLog :: Integral a => a -> a -> a > imLog b x | x | otherwise = doDiv (x`div`(b^l)) l > where l = 2 * imLog (b*b) x > doDiv x l | x | otherwise = doDiv (x`div`b) (l+1) > Integer logarithm (from Haskell report) > genArray :: Ix i => (i, i) -> (i -> a) -> Array i a > genArray r f = listArray r (map f (range r)) > Helper function (generate array using function taking index) > randArray :: Ix i => (i, i) -> RVar a -> RVar (Array i a) > randArray r v = listArray r <$> sequenceA (replicate (rangeSize r) v) > Generate array from random value generator. > sizeArray :: (Bits i, Ix (i, i), Ord i) => ((i, i), (i, i)) -> Array (i, i) i > sizeArray r = > genArray r (\(x, y) -> fromIntegral (min (findSize x) (findSize y))) > where findSize = fromIntegral . ctz > Generate array how far we should look from this point. > data FType = Box | Cross deriving (Eq, Show) > > ftypeArray :: (Bits i, Ix (i, i), Ord i, Integral i) => > (i, i) -> Array (i, i) FType > ftypeArray n = let arr = genArray ((0, 0), n) arrF > arrF (x, y) > | x == y = Box > | x == 0 || y == 0 = Cross > | x <= 2 && y <= 2 = Cross > | x > y = arr ! (x - 2^(imLog 2 x), y) > | x < y = arr ! (x, y - 2^(imLog 2 y)) > in arr > Generate array should we look on diagonals or columns/rows > fracArray :: (Bits i, Ix (i, i), Ord i, Fractional v, Integral i) > => i -> v -> RVar v -> RVar (Array (i, i) v) > fracArray n d v = do > let size = 2^n > ra <- randArray ((0, 0), (size - 1, size)) v > let s = sizeArray ((0, 0), (size, size)) > ft = ftypeArray (size, size) > arr = genArray ((0, 0), (size, size)) arrF > randF (x, y) = d*(ra ! (x, y))*2^(size - (s ! (x, y))) > average l = sum l / fromIntegral (length l) > arrF (x, y) > | x == 0 && y == 0 > = ra ! (0, 0) > | x == 0 && y == size > = ra ! (0, size) > | x == size > = arr ! (0, y) > | x == 0 > = randF (x, y) + average [arr ! (x, y - cs), > arr ! (x, y + cs), > arr ! (x + cs, x)] > | y == 0 > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y + cs)] > | y == size > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y - cs)] > | ft ! (x, y) == Cross > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y - cs), > arr ! (x, y + cs)] > | ft ! (x, y) == Box > = randF (x, y) + average [arr ! (x - cs, y - cs), > arr ! (x - cs, y + cs), > arr ! (x + cs, y - cs), > arr ! (x + cs, y + cs)] > where cs = 2 ^ (s ! (x, y)) > return arr > Any advice how to improve it? Regards PS. Am I correct that it has O(size^2) complexity i.e. O(2^n) [which is optimal]? PPS. Sorry if I sent it twice but original message seems to disappear between my computer and gmane.

1 0

lazy IO in readFile
by Andrew Sackville-West 05 Jun '10

05 Jun '10

I'm trying to suss out the best (heh, maybe most idiomatic?) way to handle laziness in a particular file operation. I'm reading a file which contains a list of rss feed items that have been seen previously. I use this list to eliminate feed items I've seen before and thus filter a list of new items. (it's a program to email me feed items from a couple of low frequency feeds). So, the way I do this is to open the history file with readFile, read it into a list and then use that as a parameter to a filter function. Instead of getting confusing, here is some simple code that gets at the nut of the problem: import Control.Monad isNewItem :: [String] -> String -> Bool isNewItem [] = \_ -> True isNewItem ts = \x -> not (any (== x) ts) filterItems :: [String] -> [String] -> [String] filterItems old is = filter (isNewItem old) is getOldData :: IO [String] getOldData = catch (liftM lines $ readFile "testfile") (\_ -> return []) main = do let testData = ["a", "b", "c", "d"] :: [String] currItems <- getOldData let newItems = filterItems currItems $ testData print newItems -- this is important, it mimics another IO action I'm -- doing in the real code... appendFile "testfile" . unlines $ newItems Please ignore, for the moment, whatever *other* problems (idiomatic or just idiotic) that may exist above and focus on the IO problem. This code works fine *if* the file "testfile" has in it some subset of the testData list. If it has the complete set, it fails with a "resource busy" exception. Okay, I can more or less understand what's going on here. Each letter in the testData list gets compared to the contents of the file, but because they are *all* found, the readFile call never has to try and fail to read the last line of the file. Thus the file handle is kept open lazily waiting around not having reached EOF. Fair enough. But what is the best solution? One obvious one, and the one I'm using now, is to move the appendFile call into a function with guards to prevent trying to append an empty list to the end of the file. This solves the problem not by forcing the read on EOF, but by not bothering to open the file for appending: writeHistory [] = return () writeHistory ni = appendFile "testfile" . unlines $ ni And this makes some sense. It's silly to try to write nothing to a file. But it also rubs me the wrong way. It's not solving the problem directly -- closing that file handle. So there's my question, how can I close that thing? Is there some way to force it? Do I need to rework the reading to read one line ahead of whatever I'm testing against (thereby forcing the read of EOF and closing the file)? thanks A --

4 10

Fractal map generator in Haskell - can it be simplified?
by Maciej Piechotka 05 Jun '10

05 Jun '10

I tried to implement fractal map generator in Haskell. While the code is correct (I believe) it is not nice: > {-# LANGUAGE FlexibleContexts #-} > import Control.Applicative > import Data.Array > import Data.Bits > import Data.Foldable > import Data.Ix > import Data.Random > import Data.Traversable > import Debug.Trace > import Text.Printf > import Prelude hiding (sum) > > ctz :: Bits a => a -> Int > ctz x@0 = bitSize x > ctz x = let ctz' n | x .&. bit n /= 0 = n > | otherwise = ctz' (n+1) > in ctz' 0 > Count trailing zeros. > imLog :: Integral a => a -> a -> a > imLog b x | x | otherwise = doDiv (x`div`(b^l)) l > where l = 2 * imLog (b*b) x > doDiv x l | x | otherwise = doDiv (x`div`b) (l+1) > Integer logarithm (from Haskell report) > genArray :: Ix i => (i, i) -> (i -> a) -> Array i a > genArray r f = listArray r (map f (range r)) > Helper function (generate array using function taking index) > randArray :: Ix i => (i, i) -> RVar a -> RVar (Array i a) > randArray r v = listArray r <$> sequenceA (replicate (rangeSize r) v) > Generate array from random value generator. > sizeArray :: (Bits i, Ix (i, i), Ord i) => ((i, i), (i, i)) -> Array (i, i) i > sizeArray r = > genArray r (\(x, y) -> fromIntegral (min (findSize x) (findSize y))) > where findSize = fromIntegral . ctz > Generate array how far we should look from this point. > data FType = Box | Cross deriving (Eq, Show) > > ftypeArray :: (Bits i, Ix (i, i), Ord i, Integral i) => > (i, i) -> Array (i, i) FType > ftypeArray n = let arr = genArray ((0, 0), n) arrF > arrF (x, y) > | x == y = Box > | x == 0 || y == 0 = Cross > | x <= 2 && y <= 2 = Cross > | x > y = arr ! (x - 2^(imLog 2 x), y) > | x < y = arr ! (x, y - 2^(imLog 2 y)) > in arr > Generate array should we look on diagonals or columns/rows > fracArray :: (Bits i, Ix (i, i), Ord i, Fractional v, Integral i) > => i -> v -> RVar v -> RVar (Array (i, i) v) > fracArray n d v = do > let size = 2^n > ra <- randArray ((0, 0), (size - 1, size)) v > let s = sizeArray ((0, 0), (size, size)) > ft = ftypeArray (size, size) > arr = genArray ((0, 0), (size, size)) arrF > randF (x, y) = d*(ra ! (x, y))*2^(size - (s ! (x, y))) > average l = sum l / fromIntegral (length l) > arrF (x, y) > | x == 0 && y == 0 > = ra ! (0, 0) > | x == 0 && y == size > = ra ! (0, size) > | x == size > = arr ! (0, y) > | x == 0 > = randF (x, y) + average [arr ! (x, y - cs), > arr ! (x, y + cs), > arr ! (x + cs, x)] > | y == 0 > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y + cs)] > | y == size > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y - cs)] > | ft ! (x, y) == Cross > = randF (x, y) + average [arr ! (x - cs, y), > arr ! (x + cs, y), > arr ! (x, y - cs), > arr ! (x, y + cs)] > | ft ! (x, y) == Box > = randF (x, y) + average [arr ! (x - cs, y - cs), > arr ! (x - cs, y + cs), > arr ! (x + cs, y - cs), > arr ! (x + cs, y + cs)] > where cs = 2 ^ (s ! (x, y)) > return arr > Any advice how to improve it? Regards PS. Am I correct that it has O(size^2) complexity i.e. O(2^n) [which is optimal]?

1 0

Re: [Haskell-beginners] Space leak debugging
by Philip Scott 04 Jun '10

04 Jun '10

On 03/06/2010 22:58, Markus Läll wrote: > I'm going to guess, that the testing i for equality forces it to be > evaluated to a integer on every iteration, so it wont grow a recursive > i + 1 + 1 + ... thunk. > > Spot on! Thank you ever so much.

1 0

Space leak debugging
by Philip Scott 04 Jun '10

04 Jun '10

Hello again, it's me, your favourite haskell beginner :) This one really has me puzzled. I've got a little example here - the program itself is a bit silly but it illustrates my problem nicely. He's a little program: import qualified Data.ByteString as B chunkFiller i bs = do if (B.null bs ) then return 1 else chunkFiller (i+1) bs main = do let bs = (B.singleton 10) j <- chunkFiller 0 bs return 1 It runs forever, which is fine, but it doesn't run in constant space. In fact, it gobbles up all the memory until it can't get any more and dies. I can't for the life of me work out what is going on, surely there is some enormous thunk being built up somewhere, but for all the Debug.Trace(), $!, seq's, and profilign outputs in the world I can't figure out where. What is *really* interesting is that if you replace the 'if' line with if (B.null bs || i== -1) then return 1 (i never equals -1) then it runs in constant space! That just boggles my mind. As usual, any thoughts greatly appreciated. All the best, Philip

3 3

Simple Chess Program for Learning FP
by Jordan Cooper 02 Jun '10

02 Jun '10

FP newbie here, I'd like to start learning how to program more purely. Immutability is something that tends to confuse me when it comes to handling state, and I figure the only way I'll understand is if I do it myself. In the past I coded a little chess game in C, where two computers played each other (not well, but they made legal moves). I figured this might be good to try and accomplish the same thing in Haskell. Any general advice before I embark would be appreciated, though my main question has to do with data structures. In C I used a two-dimensional array to represent the board (I realize there are more efficient representations, but I'm aiming for understanding over performance). I'm not sure what the natural functional equivalent would be, seeing as how arrays are immutable. Tips appreciated! Thanks, J

6 8

Installing GHC and GHCi on a PowerPC Mac running MacOS 10.5.8
by Paul Higham 01 Jun '10

01 Jun '10

I am a complete newbie but fascinated by the Haskell language. I am trying to install GHC and GHCi on an older Mac and it seems like the recommended Haskell Platform is not supported on PowerPC running MacOS 10.5.8. Is this correct? I find that following the links on the site http://haskell.org/ghc/distribution_packages.html#macosx just sends me in circles so I am appealing to you for some hints as to how to proceed. I already have XCode 3.1 installed and I have just updated my MacPorts installation but now I confess I am a bit stuck. Can you recommend a reasonable path to follow from here? Thanx ::paul

4 3