November 2007 - Haskell-Cafe

Re: Semantics of uniqueness types for IO
by Edsko de Vries 02 Nov '07

02 Nov '07

Hey, Just to continue the academic nitpicking.. :-) > Linear logic/typing does not quite capture uniqueness types since a term > with a unique type can always be copied to become non-unique, but a linear > type cannot become unrestricted. Actually, that isn't quite accurate. In linear logic, a term with a non-linear type can always be regarded as having a linear type, i.e. U -o !U is a theorem (my favourite reading of this theorem is "if you have an unlimited supply of bank notes, then you also have a single one"). The implication in the opposite direction is a falsity (from the fact that we have a single bank note, we cannot decude that we have an unlimited supply). By contrast, in uniqueness typing we certainly don't want to allow treat a term with a non-unique type as having a unique type, but we *may* want to allow to treat a term with a unique type as having a non-unique type (as you mention). However, you have to be very careful when you do that: if you allow to treat functions with a unique type as having a non-unique type, you loose all uniqueness guarantees unless you indicate in the type of the term whether or not the function has any unique elements in its closure. If you don't, you could for example construct a term that duplicates unique elements using dup x = (\f -> (f _|_, f _|_)) (\y -> x) (which would get type "forall a, unique a to pair of unique a's" if you allow to copy unique functions and then apply them). Edsko

2 4

Re: Why can't Haskell be faster?
by Jeff.Harper＠handheld.com 02 Nov '07

02 Nov '07

Peter Hercek wrote: > * it is easy to mark stuff strict (even in function signatures > etc), so it is possible to save on unnecessary CAF creations Also, the Clean compiler has a strictness analyzer. The compiler will analyze code and find many (but not all) cases where a function argument can be made strict without changing the behavior of the program.

28 47

Hiding side effects in a data structure
by C Rodrigues 02 Nov '07

02 Nov '07

While thinking about how to generate unique integer IDs on demand without using a state variable, I came up with an interesting design pattern. It's a way of doing side-effecting computation outside IO. Referential transparency is preserved by making the side effects spatial rather than temporal: by hiding side effects behind lazy thunks in a data structure, they can be disguised as the output of a single, apparently nondeterministic IO function used to data structure. This lets pure code use nondeterministic computation without the monadic plumbing required to maintain state. The getContents function works this way, but I came up with a more interesting example. The code below is a source of unique integer IDs that is modeled after the RandomGen class. It uses unsafeInterleaveIO under the hood, preserving referential transparency but not determinism. It seems to work. However, I'm not entirely sure how safe my use of unsafeInterleaveIO is. In particular, could the two branches of the tree get CSE'd? I'm also curious what people think about the general design pattern. module Unique where import Control.Monad(liftM) import Data.IORef import System.IO.Unsafe -- The goal is to produce an infinite tree of integers where each node in the -- tree has a unique value. type Unique = Int data Supply = Supply Unique Supply Supply -- The tree can be used in a stateful manner as a source of unique integers. getUnique :: Supply -> (Unique, Supply) getUnique (Supply u s1 _) = (u, s1) -- The tree can also be split into independent sources of unique integers. split :: Supply -> (Supply, Supply) split (Supply _ s1 s2) = (s1, s2) -- The catch is, the tree will probably be visited very sparsely, with most of -- it being skipped. Assigning every node its own integer is very bad, because -- that will waste most of the 2^32 available integers very quickly. In fact, -- it can get used up in just 32 calls to getUnique. -- -- Instead, we'll create a tree where integers magically appear only in places -- where they are actually used. -- First, we need an IO-bound supply of integers. newtype IOSupply = IOSupply (IORef Unique) newIOSupply :: IO IOSupply newIOSupply = liftM IOSupply $ newIORef 0 getUniqueIO :: IOSupply -> IO Unique getUniqueIO (IOSupply s) = do u <- readIORef s writeIORef s $ u+1 return u -- Now we'll use the IO-bound supply to create a tree having the desired -- properties. {-# NOINLINE getPureSupply #-} getPureSupply :: IOSupply -> IO Supply getPureSupply s = do s1 <- unsafeInterleaveIO $ getPureSupply s s2 <- unsafeInterleaveIO $ getPureSupply s n <- unsafeInterleaveIO $ getUniqueIO s return $ Supply n s1 s2 _________________________________________________________________ Climb to the top of the charts! Play Star Shuffle: the word scramble challenge with star power. http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_oct

14 21

using an external application
by Petr Hoffmann 02 Nov '07

02 Nov '07

Hi, I'm solving the following problem - I need to use an external application - give it the input data and receive its output. However, when multiple calls are made, the results are not as expected. The simplified version of the problem is given below: import System.Cmd main = do System.Cmd.system "echo hello >output.txt" -- use the external application to create an output file o1 <- readFile "output.txt" System.Cmd.system "echo bye >output.txt" -- the second call to the external application o2 <- readFile "output.txt" putStr o1 -- "hello" expected, but "bye" printed return 0 Can you please give me some hint to solve this problem? I'm a beginning haskell developer and I'm still a bit confused by the IO monad. Thank you in advance. Petr

9 10

Re: [Haskell-cafe] using an external application
by Andrew Butterfield 02 Nov '07

02 Nov '07

> On 11/2/07, Petr Hoffmann <spy.hunter(a)email.cz> wrote: > >> import System.Cmd >> main = do >> System.Cmd.system "echo hello >output.txt" -- use the external >> application to create an output file >> o1 <- readFile "output.txt" >> System.Cmd.system "echo bye >output.txt" -- the second call to >> the external application >> o2 <- readFile "output.txt" >> putStr o1 -- "hello" expected, but "bye" printed >> return 0 >> >> Can you please give me some hint to solve this problem? >> I'm a beginning haskell developer and I'm still a bit confused >> by the IO monad. >> > > I'm puzzled - when I run this on GHCi (v6.4, Windows XP) I get the following outcome *Main>main The process cannot access the file because it is being used by another process. hello *Main> This is certainly the behaviour I would expect - seeing "bye" being printed seems to me to be an error and may even constitute a violation of referential transparency. What implementation of GHC are you using ? > This looks like yet another case of the lazy-I/O goblins. > Yes, but not quite what everyone has being addressing.... -- -------------------------------------------------------------------- Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 Foundations and Methods Research Group Director. Course Director, B.A. (Mod.) in CS and ICT degrees, Year 4. Department of Computer Science, Room F.13, O'Reilly Institute, Trinity College, University of Dublin, Ireland. http://www.cs.tcd.ie/Andrew.Butterfield/ --------------------------------------------------------------------

3 2

Slightly off-topic
by PR Stanley 02 Nov '07

02 Nov '07

Hi folks Apologies for the off-topic post. If anyone knows anything about the rules of proof by deduction and quantifiers I'd be grateful for some assistance. Much obliged, Paul

3 2

do/if/then/else confusion
by David Carter 02 Nov '07

02 Nov '07

Another newbie question, but I can't seem to find any answers on the web... Can someone tell me what's wrong with this? import qualified System.Posix.Directory as PD readdirAll :: PD.DirStream -> IO [String] readdirAll d = do dir <- PD.readDirStream d if dir == "" then return [] else rest <- readdirAll d return (dir:rest) Compiling with GHC 6.6.1 gives me the not-very-useful message "Parse error in pattern", pointing to the "i" of "if". I've tried all kinds of alternative indentations (including indenting the "else" more), bracketings etc, but nothing helps. Thanks David -- The Wellcome Trust Sanger Institute is operated by Genome Research Limited, a charity registered in England with number 1021457 and a company registered in England with number 2742969, whose registered office is 215 Euston Road, London, NW1 2BE.

5 5

Need help from a newby
by karle 02 Nov '07

02 Nov '07

My declaration is as followed:- type Address = Int data Port = C | D deriving(Eq,Show) data Payload = UP[Char] | RTDP(Address,Port) deriving(Eq,Show) data Pkgtype = RTD | U deriving(Eq,Show) type Pkg = (Pkgtype,Address,Payload) type Table = [(Address,Port)] findport::[Pkg]->[Table]->[([Pkg],[Pkg])] findport [(pt,ad,pa)] [(a,p)] | ( p == C) = ([pt,ad,a],[]) | otherwise = ([],[pt,ad,a]) Error received:- Type error in explicitly typed binding *** Term : [(a,p)] *** Type : [(a,b)] *** Does not match : [Table] Can anyone please help? -- View this message in context: http://www.nabble.com/Need-help-from-a-newby-tf4735009.html#a13540531 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 4

Disjunctive Normal Form
by Jim Burton 01 Nov '07

01 Nov '07

I am trying to rewrite sentences in a logical language into DNF, and wonder if someone would point out where I'm going wrong. My dim understanding of it is that I need to move And and Not inwards and Or out, but the function below fails, for example: > dnf (Or (And A B) (Or (And C D) E)) And (Or A (And (Or C E) (Or D E))) (Or B (And (Or C E) (Or D E))) data LS = Var | Not LS | And LS LS | Or LS LS --convert sentences to DNF dnf :: LS -> LS dnf (And (Or s1 s2) s3) = Or (And (dnf s1) (dnf s3)) (And (dnf s2) (dnf s3)) dnf (And s1 (Or s2 s3)) = Or (And (dnf s1) (dnf s2)) (And (dnf s1) (dnf s3)) dnf (And s1 s2) = And (dnf s1) (dnf s2) dnf (Or s1 s2) = Or (dnf s1) (dnf s2) dnf (Not (Not d)) = dnf d dnf (Not (And s1 s2)) = Or (Not (dnf s1)) (Not (dnf s2)) dnf (Not (Or s1 s2)) = And (Not (dnf s1)) (Not (dnf s2)) dnf s = s Thanks, Jim -- View this message in context: http://www.nabble.com/Disjunctive-Normal-Form-tf4733248.html#a13534567 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

5 6

Embedding the GHC API
by Joel Reymont 01 Nov '07

01 Nov '07

Has anyone tried to embed GHC as a library recently? What is the size of the resulting binary? I'm assuming a bare minimum of needed libraries. Thanks, Joel -- http://wagerlabs.com

4 3