Re: [Haskell-cafe] Rank N type tutorial?
Greg Buchholz wrote: I'm not quite sure why this is illegal... foo :: Integer - (forall a. Show a = a) foo 2 = [foo] foo x = x ...while this is just fine... bar :: Integer - (forall a. Show a = a-b) - b bar 2 k = k [bar] bar x k = k x The way to think about it is that foralls are extra function arguments. Your first example is like foo :: Integer - (a::Type - Show a - a) so a is chosen by the caller, not by you. The second case is like bar :: Integer - (a::Type - Show a - a - b) - b In order for the first case to work as you expect, you'd need the type foo :: Integer - (a::Type, Show a, a) which is traditionally written foo :: Integer - (exists a. Show a = a) -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Fractional/negative fixity?
I'm surprised that no one has mentioned showsPrec and readsPrec. Anything more complicated than negative fixities would require their interfaces to be changed. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] File path programme
Isaac Jones wrote: You might be interested in the new FilePath module that's in the works. There's been a lot of work to make these functions portable. http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/libraries/base/System/FilePath.hs I didn't realize this was in CVS. IMHO this library is deeply broken, and should not be in GHC 6.4. We should be replacing ill-specified hacks with a carefully designed library, not an official collection of ill-specified hacks. It took me only a few minutes to find a bunch of cases which the CVS code mishandles, ranging from simple bugs, to cases where the existing behavior might be okay if documented, to cases where I'm not convinced there's any sensible behavior consistent with the function's type. (Win32) splitFileName server\\share == (server,share) (should probably be (server\\share,)) splitFileName foo:xyz == (foo:.,xyz) (should be (.,foo:xyz) -- this refers to the named stream xyz of foo) joinPaths c:\\ \\foo == \\foo (should be c:\\foo. I realize that cd c:\\ on Windows doesn't actually make c:\\ the current directory, but ; doesn't separate shell commands either.) (Posix) splitFileName /foo == (/,foo), splitFileName /foo/ == (/foo,) (arguably makes sense, but why isn't it documented?) splitFileName /foo/bar == (/foo,bar) splitFileName /foo//bar == (/foo/,bar) (definitely a bug) pathParents /foo///bar == [/,/foo,/foo,/foo,/foo/bar] pathParents foo/../bar == [.,foo/../bar] (what if foo doesn't exist and we wanted to create it?) Add to those the fundamental problems with splitFileExt which were already mentioned on this thread. I don't even think the broad approach taken by the library interface is right. Manipulating pathnames with FilePath-FilePath functions is like refactoring a Haskell module with String-String functions. There should be parsing and serialization functions which convert between the external FilePath representation and an internal ADT, and the manipulation should happen on the ADT. Please, let's not ship this with the hierarchical libraries. It's not ready for prime time. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell programs in C
Mark Carroll wrote: Wasn't there someone mentioning here a little while ago some project where they strip most of System.* from the libraries and get something that might be suitable for embedded applications? What was that called? Anyone remember? hOp: http://www.macs.hw.ac.uk/~sebc/hOp/ -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] File path programme
Jules Bean wrote: [...] it is an extension of the notion that /foo/ and /foo refer to the same directory. (Except, apparently, in the presence of symbolic links... or so I have some vague memory) Yes, /foo/ is equivalent to /foo/., which is not always the same as /foo. If /foo is a symlink, then lstat(/foo/, ...) will stat the directory at the other end, not the symlink. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] File path programme
robert dockins wrote:
After the discussion about file paths over the last several days I
went home and put together a quick trial implementation for unix file
paths, with the idea of adding windows, SMB and maybe VMS (why not?) paths.
This is great. Comments below.
data PathRoot
= UnixFilesystemRoot
| WindowsDrive Char
| SMBShare String String
| VMSDevice String
| ... -- whatever else we need
I would say that all paths are relative to something, whether it's the
Unix root, or the current directory, or whatever. Therefore I would call
this something like PathStart, and add:
| CurrentDirectory
| CurrentDirectoryOfWindowsDrive Char
| RootOfCurrentWindowsDrive
What is a pathname, broadly speaking? Answer: it's a description of a
path in a directed graph with labeled edges. It consists of a single
node designator (the starting point) and a sequence of edge designators,
i.e.
data Pathname =
Pathname {
pathStart :: PathStart,
pathEdges :: [String]
}
Most of the time all we care about is either the final node or the final
edge that we reach by following the path. The only reason we specify the
rest of the path is that there are only a few nodes that we can name
directly; to refer to any other location on the graph we have to give
driving directions from one of those nodes. There's no reason the OS
couldn't make nodes and edges first-class entities--it would solve a
multitude of problems--but most don't, so forget that.
On Unix, there are two nodes we can name directly, the root and the
current directory. On Windows, there are 26 roots and 26 current
directories which we can name directly; additionally we can name the
root or current directory of the current drive, which is one of those
26, and there are an arbitrary number of network share roots, and \\.\,
and perhaps some other stuff I don't know about.
Symbolic links complicate things a bit, since they are followed like
edges but are actually paths (so they may be affected by seemingly
unrelated changes to the graph). They're rather like VPNs, actually,
though I'm not sure how far I want to push that analogy.
Whether we're talking about the final node or the final edge depends on
the OS call; this is the usual pointer-vs-pointee confusion that's also
found in most programming languages outside the ML family. Probably we
can ignore it, with the exception of the /foo vs /foo/ distinction,
which we must preserve. This can probably be handled by parsing the
latter as Pathname { pathStart = UnixFilesystemRoot, pathEdges =
[foo,.] }.
class (Show p) = Path p where
Okay, I'm not convinced that a Path class is the right approach. For the
reasons given above, I think I'd rather have a single Path datatype,
probably with its data constructors exported. What do we gain with the
class approach? Well...
(A) Functions that accept paths can be polymorphic on the path type
(where String is a path type).
(B) We can have different datatypes for the paths of different
operating systems.
It seems like these are two very different problems which should be
solved with different typeclasses, if they're to be solved with
typeclasses at all. I think (A) can be solved very simply, and
independently of the specification of a path-handling library:
class IsPath a where
withCPath :: a - (Ptr CChar - IO b) - IO b
instance IsPath String where
withCPath = withCString -- tricky i18n issues!
instance IsPath [CChar] where
withCPath = withArray0 0
instance IsPath PathADT where
withCPath = withCString . pathToString
instance IsPath (Ptr CChar) where
withCPath = flip ($)
openFile :: (IsPath p) = p - ...
I'm tentatively opposed to (B), since I think that the only interesting
difference between Win32 and Posix paths is in the set of starting
points you can name. (The path separator isn't very interesting.) But
maybe it does make sense to have separate starting-point ADTs for each
operating system. Then of course there's the issue that Win32 edge
labels are Unicode, while Posix edge labels are [Word8]. Hmm.
isAbsolute :: p - Bool
Definition: a path is absolute if its meaning is independent of (Posix:
the current directory) (Win32: all current directories and the current
drive).
pathCleanup :: p - p -- remove .. and suchlike
This can't be done safely except in a few special cases (e.g. /.. -
/). I'm not sure it should be here.
hasExtension :: p - String - Bool
This is really an operation on a single component of the path. I think
it would make more sense to make it an ordinary function with type
String - String - Bool and use the basename method to get the
appropriate path component.
pathToForeign :: p - IO (Ptr CChar)
pathFromForeign :: Ptr CChar - IO p
This interface is problematic. Is the pointer returned by pathToForeign
a heap pointer which the caller is supposed to free? If so, a Ptr CChar
instance would have to
Re: [Haskell-cafe] The Nature of Char and String
John Goerzen wrote: Char in Haskell represents a Unicode character. I don't know exactly what its size is, but it must be at least 16 bits and maybe more. String would then share those properties. However, usually I'm accustomed to dealing with data in 8-bit words. So I have some questions: Char and String handling in Haskell is deeply broken. There's a discussion ongoing on this very list about fixing it (in the context of pathnames). But for now, Haskell's Char behaves like C's char with respect to I/O. This is unlikely ever to change (in the existing I/O interface) because it would break too much code. So the answers to your questions are: * If I use hPutStr on a string, is it guaranteed that the number of 8-bit bytes written equals (length stringWritten)? Yes, if the handle is opened in binary mode. No if not. + If yes, what happens to the upper 8 bits? Are they simply stripped off? Yes. * If I run hGetChar, is it possible that it would consume more than one byte of input? No in binary mode, yes in text mode. * Does Haskell treat the this is a Unicode file marker special in any way? No. * Same questions on withCString and related String-CString conversions. They all behave as if reading/writing a file in binary mode. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: File path programme
Peter Simons wrote: The module currently knows only _relative_ paths. I am still experimenting with absolute paths because I have recently learned that on Windows something like C:foo.txt is actually relative -- not absolute. Very weird. \foo.txt is also relative on Win32. And con.txt is absolute. There also is a function which changes a path specification into its canonic form, meaning that all redundant segments are stripped. So although two paths which designate the same target may not be equal, they can be tested for equivalence. Again, while this transformation may be useful in some cases, it is not a canonicalization operation. foo/../bar and bar do not in general refer to the same file, and foo and foo/. are not in general equivalent. We shouldn't encourage these misconceptions in the library, even if we do provide a path-collapsing transformation along these lines. Other comments: The Read and Show instances aren't inverses of each other. I don't think we should be using Read for path parsing, for this reason. I don't understand why the path ADT is parameterized by segment representation, but then the Posix and Windows parameter types are both wrappers for String. It seems artificial to distinguish read :: String - RelPath Windows from read :: String - RelPath Posix in this way. In general, this library doesn't seem to deal with any of the hard cases. The devil's in the details. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parity of the number of inversions of a permutation
Henning Thielemann wrote: I' searching for a function which sorts the numbers and determines the parity of the number of inversions. I assume that there are elegant and fast algorithms for this problem (n * log n time steps), e.g. a merge sort algorithm. This is a rather nice little problem. I think this works: countInversions :: (Ord a) = [a] - Int countInversions [] = 0 countInversions xs = snd $ foldb merge [([x],0) | x - xs] merge :: (Ord a) = ([a],Int) - ([a],Int) - ([a],Int) merge (xs,a) (ys,b) = case merge' (length xs) xs ys of (zs,c) - (zs,a+b+c) merge' 0 [] ys = (ys,0) merge' n xs [] = (xs,0) merge' n (x:xs) (y:ys) = case compare x y of LT - case merge' (n-1) xs (y:ys) of (zs,c) - (x:zs,c) GT - case merge' n (x:xs) ys of (zs,c) - (y:zs,c+n) EQ - undefined foldb :: (a - a - a) - [a] - a foldb f [] = undefined foldb f [x] = x foldb f xs = foldb f (foldb' f xs) foldb' f (x1:x2:xs) = f x1 x2 : foldb' f xs foldb' f xs = xs -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Growing Trees
[Previously sent only to the OP -- oops]
Tom Hawkins wrote:
data Tree a
= TreeRoot { stuff:: a
, children :: [Tree]
}
| TreeNode { stuff:: a
, parent :: Tree
, children :: [Tree]
}
But because of these bidirectional links, every time I add a node I must
reconstructing the entire tree.
If you don't want to use IORefs or STRefs, you could try The Zipper:
http://www.haskell.org/hawiki/TheZipper
or you could represent the tree as
type Tree a = Data.Map.Map Int (Node a)
data Node a = TreeRoot { stuff :: a, children :: [Int] }
| TreeNode { stuff :: a, parent :: Int, children :: [Int] }
-- Ben
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question on Haskell type
Cale Gibbard wrote: As an example of this sort of thing, I know that there are only 4 values of type a - Bool (without the class context). They are the constant functions (\x - True), (\x - False), and two kinds of failure (\x - _|_), and _|_, where _|_ is pronounced bottom and represents something along the lines of nontermination (aborting the program also counts). Don't forget (\x - x `seq` True) and (\x - x `seq` False). -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] newtype is superfluous
Wolfgang Jeltsch wrote: This is not true. With newtype, A _|_ is _|_, with data, A _|_ is not _|_. It's probably more helpful to explain this in terms of a program that exhibits different behavior in the two cases: case error data of A x - newtype But as far as I know, the above newtype declaration is equivalent to this: data A = A !Int Nope: case A (error data!) of A x - data or newtype -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Two questions: lazy evaluation and Church-Rosser
Gregory Woodhouse wrote: I've been trying to do some background reading on lambda calculus, and have found discussions of strict evaluation strategies (call-by-value and call-by-name) but have yet to find an appropriate framework for modeling lazy evaluation Just wanted to point out that call-by-name is non-strict. Lazy evaluation is basically just call-by-name with extra sharing; if you only care about semantics and not time/space behavior, it's the same as call-by-name. (much less infinite lists and comprehensions). In a lazy or call-by-name operational semantics, you never get infinite lists, just lists with unevaluated tails which get unwrapped as needed. List comprehensions in Haskell are syntactic sugar. The Haskell 98 report explains how to transform them away. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Existentially-quantified constructors, Eq and Show
John Meacham wrote: PS. many, including me, feel 'forall' is a misnomer there and should be the keyword 'exists' instead. so just read 'foralls' that come _before_ the type name as 'exists' in your head and it will make more sense. I disagree. When you write forall a. D (P a) (Q a) it means that there's a variant of D for all types a. It's as though you had D (P Bool) (Q Bool) | D (P String) (Q String) | ... Writing exists instead would mean that there's only one version of D for some a, and you don't know what that a is; in that case you could only safely apply D to arguments of type (forall b. P b) and (forall b. Q b). I think the problem is not with the use of forall, but with the use of the term existential type. The fact that existential quantification shows up in discussions of this language extension is a red herring. Even Haskell 98 has existential types in this sense, since (forall a. ([a] - Int)) and ((exists a. [a]) - Int) are isomorphic. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Shootout favouring C
Isaac Gouy wrote: Please keep to the true spirit of fictional crime writing and provide a motive for these evil characters who will stop at nothing to make Haskell seem some worse than C. Erm, fictional? It strikes me that this particular brand of evil is more the norm than the exception. I think Bjarne Stroustrup put it quite well: http://public.research.att.com/~bs/bs_faq.html#compare That said, I see nothing to suggest that such is happening here. I do have objections to the shootout, but they're objections to the whole concept of benchmarks in general, not to these particular ones. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Guess what ... Tutorial uploaded! :)
Dmitry Astapov wrote: http://www.haskell.org/hawiki/HitchhickersGuideToTheHaskell I like the approach too, but the section on IO actions, which I'm reading now, is not correct. It's not true that a - someAction has the effect of associating a with someAction, with the actual work deferred until later. All of the IO associated with someAction happens at the program point where a - someAction appears, whether or not it's needed later. getContents is a rare exception to this rule. It works by using unsafeInterleaveIO behind the scenes, which muddies Haskell's generally clean semantics and leads to odd impure behavior. I wish getContents were a good example of nonstrictness or laziness, but I don't think it is. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: strict Haskell dialect
Chris Kuklewicz wrote:
Weak uses seq to achieve WHNF for it's argument
newtype Weak a = WeakCon {runWeak :: a}
mkWeak x = seq x (WeakCon x)
unsafeMkWeak x = WeakCon x
This doesn't actually do what you think it does. mkWeak and unsafeMkWeak are
the same function.
mkWeak 123 = seq 123 (WeakCon 123) = WeakCon 123
unsafeMkWeak 123 = WeakCon 123
mkWeak _|_ = seq _|_ (WeakCon _|_) = _|_
unsafeMkWeak _|_ = WeakCon _|_ = _|_
To quote John Meacham:
| A quick note,
| x `seq` x
| is always exactly equivalant to x. the reason being that your seq
| would never be called to force x unless x was needed anyway.
|
| I only mention it because for some reason this realization did not hit
| me for a long time and once it did a zen-like understanding of seq
| (relative to the random placement and guessing method I had used
| previously) suddenly was bestowed upon me.
I remember this anecdote because when I first read it, a zen-like
understanding of seq suddenly was bestowed upon /me/. Maybe it should be in
the docs. :-)
-- Ben
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why is $ right associative instead of left associative?
No one has mentioned yet that it's easy to change the associativity of $ within a module in Haskell 98: import Prelude hiding (($)) infixl 0 $ f$x = f x or, for the purists, import Prelude hiding (($)) import qualified Prelude (($)) infixl 0 $ ($) = (Prelude.$) -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why is $ right associative instead ofleftassociative?
Paul Hudak wrote: Minor point, perhaps, but I should mention that : is not special syntax -- it is a perfectly valid infix constructor. But Haskell 98 does treat it specially: you can't import Prelude hiding ((:)), or rebind it locally, or refer to it as Prelude.:. In fact I've always wondered why it was done this way. Can anyone enlighten me? Of course it might be confusing if it were rebound locally, but no more confusing than the fact that [f x | x - xs] is not the same as (map f xs). It might be kind of nice if the list type were actually defined in the Prelude as data List a = Nil | a : List a and all of the special [] syntax defined by a desugaring to this (entirely ordinary) datatype, e.g. [1,2] - 1 Prelude.: 2 Prelude.: Prelude.Nil. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why is $ right associative instead of leftassociative?
Tomasz Zielonka wrote: On Sun, Feb 05, 2006 at 01:14:42PM -, Brian Hulley wrote: How about: f x y . g x $ z But then you have a problem when you when you want to add something at the beginning ;-) How about: id . f x y . g x $ z -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: extending bang proposal Re: strict Haskell dialect
Bulat Ziganshin wrote: Hello Ketil, KM (Is the second ! actually meaningful?) yes! it means that the function is strict in its result - i.e. can't return undefined value when strict arguments are given. Unfortunately this interpretation runs pretty quickly into theoretical difficulties. A ! on the right hand side of a function arrow isn't like a ! on the left hand side. If you used this notation for this purpose, it would have to be special-cased. Note that in GHC at present, a function of type Int# - Int# can diverge. KM foo :: [!a] - ![a] - a ![a] means strict list, it is the same as defining list with next field strict: data List2 a = Nil2 | List2 a !(List2 a) This isn't consistent with the general rule that ! means absence of _|_. The semantics that you want could be implemented as a special case for the [] constructor, but polymorphism breaks this, e.g. data Foo a = MkFoo Int !a data Bar a = MkFoo Int a Foo [Bool] /= Bar ![Bool] for example, the following definition type Map a b = [(a,b)] will be instantiated to Map !Int String == [(!Int, String)] As long as you're only specializing datatypes this works fine, but when you try to do the same with polymorphic functions acting on those datatypes, you run into serious problems. E.g. f :: forall a. a - Maybe a f _ = Just undefined Now we have (f :: Int - Maybe Int) 3 == Just _|_, but (f :: !Int - Maybe !Int) 3 == _|_. This means that either f and all of its callers must be specialized at compile time (despite having no type class constraints) or f must inspect its implicit type argument at run time. such proposal already exists and supported by implementing this in GHC HEAD As Robert Dockins said, it's not implemented, and it isn't clear how to implement it. At this point it's looking fairly likely that my PhD thesis will be on this very topic, so stay tuned. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: extending bang proposal Re: strict Haskell dialect
Brian Hulley wrote: One motivation seems to be that in the absence of whole program optimization, the strictness annotations on a function's type can allow the compiler to avoid creating thunks at the call site for cross-module calls whereas using seq in the function body itself means that the thunk still has to be created at the call site because the compiler can't possibly know that it's going to be immediately evaluated by seq. GHC solves this with the worker-wrapper transformation: the code for the wrapper is exported as part of the module's interface and inlined at external call sites. It handles seq, unboxing, and so on and calls the worker via a private interface. Not that I think strictness information in the type system is a bad idea. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Matching constructors
Mark T.B. Carroll wrote: Creighton Hogg [EMAIL PROTECTED] writes: data Patootie = Pa Int | Tootie Int and I want to pull out the indices of all elements of a list that have type constructor Tootie, how would I do that? x = [Pa 3, Tootie 5, Pa 7, Tootie 9, Pa 11] y = [ i |Tootie i - x ] z = [ i | i@(Tootie _) - x ] I think this is what the OP wanted: [ i | (i,Tootie _) - zip [0..] x ] -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: -fno-monomorphism-restriction makes type-inference ambiguous?
Eike Scholz wrote: mylength = synAttr listLength $ *Main :type synAttr $ synAttr :: (Data b) = ((?stack::[Dyn]) = b - a) - Attr a $ *Main :type listLength $ listLength :: (?stack::[Dyn]) = List - Float $ *Main :type (synAttr listLength) $ (synAttr listLength) :: Attr Float $ *Main :type mylength $ mylength :: (?stack::[Dyn]) = Dyn - Dyn - [Dyn] - Maybe Float where type Attr a = Dyn - Dyn - [Dyn]- Maybe a This may be a bug. But note that both interpretations are legitimate. One way of applying synAttr to listLength is first to apply ?stack to listLength, obtaining listLength' :: List - Float and creating a (?stack::[Dyn]) constraint on the application node, then specializing listLength' to the type (?stack::a) = List - Float, then passing that to synAttr. Again, I recommend that you not try to use implicit parameters. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: PrefixMap: code review request
Brian Hulley wrote:
Whoever thought up the original Haskell layout rule assumed that people
would be happy using a single fixed width font, tabs set to 8 spaces,
and didn't care about the brittleness of the code (in the face of
identifier renamings) it allowed one to write.
Are you complaining that Haskell permits you to write code with these
problems, or that it requires you to? The latter is not true. Instead of
keyword clause1
clause2
you can always write
keyword
clause1
clause2
or
keyword { clause1
; clause2
}
Both styles are insensitive to tab width and renaming of identifiers. The
off-side rule only comes into play when you don't include an explicit {, so
you can suppress it entirely if you prefer.
If you have a different layout rule in mind I'd be interested in hearing it,
but I think Haskell's is quite good overall. Lisp has similar indentation
problems despite the lack of a layout rule, since people commonly write
(foo (...)
(...))
Renaming foo can't confuse the compiler, but I've never had a Haskell layout
error change the meaning of my program. At worst it causes the program to be
rejected.
I do edit my source code in a fixed-width font, but it's a very pretty font
(Bitstream Vera Sans Mono). It's a small price to pay for the convenience of
being able to use 2D layout, even in languages where it's not significant,
and in comments.
-- Ben
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: rounding errors with real numbers.
Henning Thielemann wrote: Maybe you should use a kind of convex combination, that is (x-oldLower)*a + (oldUpper-x)*b Maybe lower*(1-z) + upper*z where z = (x-oldLower) / (oldUpper-oldLower). I think this will always map oldLower and oldUpper to lower and upper exactly, but I'm not sure it's monotonic. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Layout rule (was Re: PrefixMap: code review request)
Brian Hulley wrote:
Here is my proposed layout rule:
1) All layout keywords (where, of, let, do) must either be followed by a
single element of the corresponding block type, and explicit block
introduced by '{', or a layout block whose first line starts on the
*next* line
I wouldn't have much trouble adapting to that.
and whose indentation is accomplished *only* by tabs
You can't be serious. This would cause far more problems than the current rule.
I would also make it that explicit braces are not allowed to switch off
the layout rule (ie they can be used within a layout),
I don't understand. What does used within a layout mean?
multiline strings would not be permitted,
They aren't now, except with \ escapes. A stray will be caught on the same
line unless the line happens to end with \ and the next line happens to
begin with \, which is exceedingly unusual.
and multiline comments would not be permitted
(pragmas could easily be used just by using --#)
But --# doesn't introduce a comment. And this would make UNPACK pragmas
rather inconvenient to use.
1) When you see a ';' you could immediately tell which block it belongs
to by looking backwards till the next '{'
I guess that might be helpful, but it doesn't seem easier than looking left
to the beginning of the current line and then up to the first less-indented
line.
2) Variable width fonts can be used,
They can be used now, if you adhere to a certain style, but not everyone
likes that style. I wrote in C++ with a variable width font and tabs at one
time, but eventually went back to fixed width. One reason was that I
couldn't use comment layout conventions that tend (in my experience) to
improve readability more than monospacing hurts it. Another reason was that
glyph widths appropriate to natural languages didn't work all that well for
source code. Spaces are much more important in source code than in natural
language, for example. A proportional font designed for source code would be
nice, but I haven't found one yet. Stroustrup used a mixture of proportional
and monospaced glyphs in _The C++ Programming Language_ and it worked well.
or different font faces to
represent different sorts of identifier eg class names, tycons, value
constructors, operators like `seq` as opposed to seq etc
Lots of editors do this with monospaced fonts; I think it's orthogonal to
the layout issue.
3) Using only tabs ensures that vertical alignment goes to the same
position on the screen regardless of the font and tabs could even have
different widths just like in a wordprocessor
Requiring tabs is a really bad idea. Just forget it. Seriously.
4) Any keypress has a localised effect on the parse tree of the buffer
as a whole ( { no longer kill everything which follows and there would
be no {- )
I don't understand why this is an advantage. If you have an editor that
highlights comments in green, then large sections of the program will flash
green while you type a {- -} comment, which might be annoying, but it also
means you'll never forget to close the comment, so the practical benefit of
forbidding {- -}, as opposed to simply not typing it yourself, seems nil.
5) It paves the way for a much more immersive editing environment, but I
can't say more about this at the moment because I haven't finished
writing it yet and it will be a commercial product :-)))
I guess everything has been leading up to this, but my reaction is that it
renders the whole debate irrelevant. The only reason layout exists in the
first place is to make source code look good in ordinary text editors. If
you have a high-level source code editor that manipulates the AST, then you
don't need layout, or tabs, or any of that silly ASCII stuff. The only time
you need to worry about layout is when interoperating with implementations
that use the concrete syntax, and then there's nothing to stop you from
exporting in any style you like. And when importing, there's no reason to
place restrictions on Haskell's layout rule, because the visual layout you
display in the editor need have no connection to the layout of the imported
file.
Using my self-imposed layout rule I'm currently editing all my Haskell
code in a standard text editor using tabs set to 4 spaces and a variable
width font and have no problems.
Which is the best argument for keeping the current rule! If it were changed
as you propose, then someday Hugh Briley would come along and complain that
Haskell's layout syntax squandered screen space---but he *wouldn't* be able
to program in his preferred style, because it would no longer be allowed.
Religious freedom is a good thing.
{- Ben -}
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Layout rule (was Re: PrefixMap: code review request)
Duncan Coutts wrote: hIDE and Visual Haskell use the ghc lexer and get near-instantaneous syntax highlighting. Hmm... I just installed Visual Haskell 0.1, and when I type in the editor, CPU usage rises to about 70% and there's a noticeable delay before each character appears on the screen. This is a very short module (~100 lines) and a Pentium M 1600 CPU. Am I doing something wrong? -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Layout rule (was Re: PrefixMap: code review request)
Benjamin Franksen wrote: TAB characters in program text should be forbidden by law. Well... they are quite useful for lining things up if you're using a proportional font, and I don't think proportionally-spaced code is a bad idea. I want them to be optional. But it would be nice if parsers would warn about (or even reject) programs whose meaning depends on tab width. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Layout rule
Ketil Malde wrote:
Multi line comments are nice for commenting out blocks of code.
They're also nice for comments within a line. E.g. haskell-src-exts contains
the declaration
data HsQualConDecl
= HsQualConDecl SrcLoc
{- forall -} [HsName] {- . -} HsContext {- = -} HsConDecl
Probably half of my uses of {- -} begin and end on the same line.
-- Ben
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Layout rule (was Re: PrefixMap: code review request)
I wrote: I just installed Visual Haskell 0.1, and when I type in the editor, CPU usage rises to about 70% and there's a noticeable delay before each character appears on the screen. This is no longer happening, so I guess I ran afoul of a bug. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: different code in different platforms
Neil Mitchell wrote: #ifdef __WIN32__ (Windows code) #else (Linux code) #endif In Yhc, we use a runtime test to check between Windows and Linux. I think the cleanest solution is to factor the OS-specific code into separate modules with OS-independent interfaces and names, and pull in the appropriate implementations at compile time by changing the module search path. That way you avoid the syntactic and semantic ugliness of cpp as well as most of the practical problems of a runtime test. You can also use any two or all three of these techniques together. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: how would this be done? type classes? existential types?
Matthias Fischmann wrote: now i want to create a list of a type similar to [r1, r2, r3] :: (Resource a) = [a] but with r1 being pizza, r2 being crude oil, and so on. The type you actually want here is [exists a. (Resource a) a], but no Haskell implementation supports that. data Rs = forall a . (Resource a) = Rs a unRs (Rs a) = a rsName :: Rs - String rsName = resourceName . unRs ... [...] but what is the type of unRs? Its type is (Rs - (exists a. (Resource a) a)), but again no Haskell implementation supports that. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: how would this be done? type classes? existentialtypes?
Matthias Fischmann wrote:
is there any difference between these
two? if they are equivalent, why the two different ways to say it?
data X where X :: (Resource a) = a - X
data Y = forall a . (Resource a) = Y a
There's no difference. There are two ways to say it for historical reasons.
The second notation dates back many years, while the first notation is new
and experimental. Only the first notation supports GADTs, and only the
second supports deriving declarations and strict fields and record syntax
(though I think this is going to change). Also the second notation is more
convenient when you're declaring an ordinary datatype---compare
data List a = Nil | Cons a (List a)
data List a where { Nil :: List a ; Cons :: a - List a - List a }
and now it gets interesting: i need instances for Rs on Show, Read,
Eq, Ord. Show is very simple, but Read?
I think you're right: it's impossible to implement Read for Rs in an
extensible way, because there's no way to obtain the necessary Resource
dictionary at runtime. I've wished in the past for a family of functions,
one for each single-parameter typeclass, with types something like
Dynamic - (forall a. C a = a - b) - Maybe b
and you'd need something similar here.
Assuming this is indeed impossible and you have to close the world of
Resources, you may as well do it by writing
data Rs = RsRice Rice | RsCrudeOil CrudeOil | ...
deriving (Show,Read,Eq,Ord)
-- Ben
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: how would this be done? type classes? existential types?
Matthias Fischmann wrote: On Thu, Mar 16, 2006 at 12:40:00PM +, Chris Kuklewicz wrote: (Why isn't it resourceName :: String ?) when i am trying this, ghc complains that the type of resourceName doesn't have any occurrance of 'a', and i feel that it must be harder for the type engine to figure things out if there isn't, so resourceName is still a mapping from resources to their names. Yes, if you had resourceName :: forall a. Resource a = String then there'd be nothing to prevent the expression (resourceName :: String) from evaluating to any resource name in any context. A trick you can pull is to define data Proxy a = Proxy and give resourceName's parameter the type Proxy a instead of a. This makes it clear that it's only the type you care about, not the value. The downside is that it tends to be less convenient to use, which is presumably why standard library functions with this problem (like floatRadix and sizeOf) don't use this solution. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: how would this be done? type classes?existential types?
Brian Hulley wrote: Is there a reason for using instead of [exists a. Resource a=a] ? Only that = looks like a function arrow, looks like a tuple. I stole this notation from an unpublished paper by SimonPJ et al on adding existential quantification to Haskell. I'm not especially attached to it. Actually I rather like forall a | Resource a. a exists a | Resource a. a a) A value 'v' of type 'exists a. Resource a=a 'would have to be internally represented as something like (dictResource_t, value_t) Yes. b) Given such a value, there is no syntactic way to distinguish the pair from the value_t stored inside it, unlike the use of 'forall' where the syntax for the constructor conveniently represents any dictionaries that have been glued onto the value (ie pattern matching against R x gives us back the dictionaries R and the plain value x)? Yes, but that doesn't necessarily mean you can't work out when to construct and deconstruct these implicit tuples. That's exactly what the type inference process does with implicit type arguments, and implicit type returns are dual to that, so the process should be similar. It is tricky, though. E.g. given (f (g z)) where f :: forall a. [a] - Int g :: String - (exists b. [b]) in principle you should be able to call g first, getting a type b and a list [b], then instantiate f with the type b, then pass the list to it, ultimately getting an Int. But I don't know how to design a type inference algorithm that will find this typing. If on the other hand f :: (exists a. [a]) - Int then it's easy to do the right thing---which is a little odd since these two types for f are otherwise indistinguishable. Hope I'm not making this more confusing but I'm still trying to get my head around all these invisible happenings regarding dictionaries so I can visualise what's happening in terms of bytes and pointers in the runtime Once you understand where the types go in System F, the dictionaries are easy: they always follow the types around. Any time you have forall a b c. (C1 a b, C2 b c) = ... in the source, you have five corresponding parameters/arguments in GHC Core, one for each type variable and constraint. These are always passed around as a unit (at least prior to optimization). In principle you could box them in a 5-tuple. The dictionary values are nothing more or less than proofs that the corresponding constraints hold. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Positive integers
Daniel McAllansmith wrote: I can see the domain bounds check would be a problem in theory, but in practice doesn't the type enforce that? Keeping Word positive costs nothing because it just overflows. Wouldn't it be much the same? If you're planning wraparound semantics then you're better off with Int indexes. Passing an index congruent to -1 mod 2^32 is certainly an error, and (!!) may as well fail immediately rather than try to traverse 2^32-1 list nodes. I think both Int and Word are equally correct here, since both are proper supersets of the valid set of indexes. (If you're working with lists so long that Int may not be big enough, you shouldn't trust Word either.) Haskell 98's List module supplies generic versions of the list functions, like genericIndex :: Integral a = [b] - a - b, which will work with Word. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Existentially-quantified constructors: Hugs is fine, GHC is not?
Otakar Smrz wrote: data ... = ... | forall b . FMap (b - a) (Mapper s b) ... where FMap qf qc = stripFMap f q the GHC compiler as well as GHCi (6.4.2 and earlier) issue an error My brain just exploded. I can't handle pattern bindings for existentially-quantified constructors. The problem here is a tricky interaction between irrefutable pattern matching and existential tuples. In Core, the FMap constructor has a third field which stores the type b, and when you match against the pattern (FMap qf qc) you're really matching against (FMap b qf qc). (stripFMap f q) might evaluate to _|_, in which case, according to the rules for irrefutable matching, all of the pattern variables have to be bound to _|_. But type variables (like b) can't be bound to _|_. From an operational standpoint, the problem is that the (fully-evaluated) value of b has to be available in the body of the let statement, which means that (stripFMap f q) must be evaluated before the body, and the let statement must diverge without reaching the body if (stripFMap f q) diverges, since no value can be assigned to b in that case. But the semantics of let clearly require that execution always proceed to the body no matter what (stripFMap f q) evaluates to. So I'm not convinced that your program is well-typed, even though it looks fine at first. I'm not sure what happens to Haskell's semantics when you allow type variables to be bound to _|_. The fact that Hugs allows it may be a bug. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: develop new Haskell shell?
Brian Hulley wrote: Donn Cave wrote: (cd /etc/stuff; cat * result) Well the problem here is that the command leaves you in /etc/stuff so you have to remember this when you subsequently execute another command. No it doesn't. The parentheses around the command sequence cause it to run in a subshell with its own private working directory. Well someone had to define the meaning of basename so if we make the definition of renif similarly built-in the comparison is between ls = mapM_ (renif txt hs) and for a in *.txt; do mv $a $(basename $a .txt); done This comparison is unfair because basename is a much more generic operation than renif. The Haskell code should be something like glob *.txt = mapM_ (\a - mv a (basename a .txt ++ .hs)) So the Haskell command is shorter, easier to read, and more re-usable, because mapM_ (renif txt hs) can be used anywhere that supplies a list of files whereas for a in *.txt doesn't make the source of the list explicit. Do they come from the current directory? What if some other list of files should be used? This makes no sense. Bash has its own set of rules. The for statement iterates over a list, which in this case is generated by a glob. If you want something else, you use the appropriate construct. The body of the for loop is just as reusable as the corresponding Haskell code. My reaction to this thread is the same as Donn Cave's: even after reading through the whole thread, I don't understand what a Haskell shell is supposed to be. It feels like people are more interested in capturing territory for Haskell than in solving any actual problem. For simple commands and pipes, the bash syntax is perfect. For anything nontrivial, I use some other language anyway. I long ago wrote a Perl script to do a far more general form of the renaming example you gave above. As far as I know, the only reason people write nontrivial /bin/sh scripts is that it's the only scripting language that's universally available on Unix systems. Even Perl isn't deployed everywhere. A Haskell shell is never going to be ubiquitous, and Haskell syntax is inferior to bash syntax for 99% of the command lines I type. On the other hand, I'm entirely in favor of extending Haskell with functions like glob :: String - IO [String]. That would be useful. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] matching constructors
On Mon, 8 Mar 2004, Vadim Zaliva wrote: I am doing command line options parsing. I've defined Flag type with constructor for each possible option: data Flag = Verbose | Input String | Output String | Filter String deriving (Show, Typeable, Data) getOpt returns me a list of such objects. Now I need to look things up there by constructor. For example: doSomething fltflag where (Filter fltflag) = findFlag (Filter none) opts Try this instead: doSomething $ option none [fltflag | Filter fltflag - opts] ... option :: a - [a] - a option def [] = def option def [x] = x option def _ = error Only one of each option allowed -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Writing binary files?
I modestly re-propose the I/O model which I first proposed last year: http://www.haskell.org/pipermail/haskell/2003-July/012312.html http://www.haskell.org/pipermail/haskell/2003-July/012313.html http://www.haskell.org/pipermail/haskell/2003-July/012350.html http://www.haskell.org/pipermail/haskell/2003-July/012352.html ... -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Maybe bytes *are* text (was Re: Writing binary files?)
On Thu, 16 Sep 2004, Udo Stenzel wrote:
Having a seperate byte based api is far better. If you don't know the
encoding, all you have is bytes, no text.
Okay, after reading large chunks of this discussion, I'm going to rock the
boat a bit by suggesting that bytes *are* text, and *do* belong in the
Char type, and hence that the current binary file API is actually correct,
after a fashion. In fact, I think that we can resolve many of the problems
of this thread by abandoning the conceptual distinction between characters
and bytes.
Suppose I invoke
gcc -o XXX YYY.c
where XXX and YYY are strings of Japanese characters. It has been pointed
out that if GCC treats its filename arguments as opaque byte strings to be
passed back to the appropriate file opening functions, then it will work
even if the current locale isn't Japanese. But that's only true on Posix-
like systems. On NT, filenames are made of Unicode code points, and argv
is encoded according to the current locale. If GCC uses argv, it will fail
on the example above. I've run into this problem many times on my desktop
XP box, which uses a US-English locale but contains some filenames with
Japanese characters in them.
But in any case GCC's arguments aren't really opaque: it needs to check
each argument to see if it's an option, and it needs to look at the
extensions of files like YYY.c to figure out which subprogram to invoke.
Nevertheless, the opaque-filename approach does work on Posix, because --
this is the important bit -- the characters GCC cares about (like '-',
'o', '.', and 'c') have the same representation in every encoding. In
other words, the character encoding is neither transparent nor opaque to
GCC, but sort of band-limited: it can understand the values from 0 to
127, but the higher values are mysterious to it. They could be Latin-1
code points; they could be EUC half-characters; they could be Unicode code
points. It doesn't know, and it doesn't *need* to know. It will fail if
given an encoding which doesn't follow this rule (e.g. EBCDIC).
We can make GCC (were it implemented in Haskell) work with all filenames
on both major platforms without platform-specific code by representing
command-line arguments and pathnames as Strings = [Char]s, where Char is
defined as the byte values 0-255 on Posix, but the UTF-16 values on Win32.
Clearly this is very fragile, but the type system provides a solution:
newtype {- TransASCIIEncoding a = -} Char a = Chr Word32
type String a = [Char a]
class TransASCIIEncoding a where
maxValueUsedByEncoding :: Word32
instance TransASCIIEncoding Unicode where ...
instance TransASCIIEncoding UTF16 where ...
instance TransASCIIEncoding UTF8 where ...
instance TransASCIIEncoding GenericByte where ...
'x' :: Char a
'\u1234' :: Char Unicode
'\q789' :: Char WeirdCompilerSupportedEncoding
instance (TransASCIIEncoding a) = Bounded (Char a) where
minBound = Chr 0
maxBound = Chr maxValueUsedByEncoding
class CharTranscoding a b where
transcode :: CharacterString a
ord :: Character a - Maybe Int -- Nothing if arg isn't ASCII
ordUnicode :: Character Unicode - Int
Obvious problems: backward compatibility and codings like ISO 2022 and
Shift-JIS which break the fundamental assumption. I don't think either
problem is fatal. A more flexible subtyping mechanism would be nice, so
that (e.g.) byte-writing functions could take any Char type with a
sufficiently small maxValue.
-- Ben
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OO idioms redux
On Tue, 12 Oct 2004, John Goerzen wrote: One of the best features of OO programming is that of inheritance. It can be used to slightly alter the behavior of objects without requiring modification to existing code or breaking compatibility with existing APIs. I hesitate to express a contrary opinion since it'll sound as though I'm defending Haskell's limitations, but that's actually not the case here -- this was true even before I learned Haskell. In my own OOP code (mainly C++) I've rarely used implementation inheritance, and when I have I've never felt entirely happy about the way it turned out; it always seemed a bit fragile and hacky. When I want to take advantage of polymorphism I usually use abstract interfaces, and when I want to share code I usually use containment and delegation, which has always struck me as more robust. In any case, Haskell does support polymorphic abstract interfaces and containment and delegation. In your ConfigParser example you would have an interface (say IConfigParser) which would be represented as a type class, and two implementations (ConfigParser and EnvConfigParser) which would be represented as instances of the type class. E.g. class IConfigParser a where newConfigParser :: IO a readConfigFile :: a - FilePath - IO () getFoo :: a - IO Foo setFoo :: a - Foo - IO () ... data ConfigParser = ... instance IConfigParser ConfigParser where ... data EnvConfigParser = ECP ConfigParser instance IConfigParser EnvConfigParser where newConfigParser = liftM ECP newConfigParser readConfigFile (ECP cp) path = readConfigFile cp path envSubst cp getFoo (ECP cp) = getFoo cp ... I should say, though, that this is very unidiomatic code. Partly this is because I don't quite understand the meaning of your ConfigParser class -- does it exist before a configuration file is read? What is the meaning of having more than one instance? Parsing configuration files strikes me as more verb than noun, and I'd be more inclined in this case to declare a single ConfigData type, a single function to write it to a file, and two functions to read it, one with environment substitution and one without. So I suppose my advice is twofold: 1. Try replacing implementation inheritance with containment and delegation when you translate to Haskell. 2. Try revisiting the original problem and thinking about how to solve it in a Haskellish way, rather than solving it in another language and then translating. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] lazy constructors
Serge D. Mechveliani wrote: As the types are resolved before the computation, as the above program shows, how can addToSPair expect anything besides a string pair? Why tilda is not a default? Haskell pairs are lifted, meaning that they also include an extra value (bottom) which doesn't match (x,y). Not everyone is convinced that this is a good idea, but it's the way things are at present. The only doubt may be the matching of (xs, ys) against bottom :: (String, String) Is not this natural to have a result as (bottom :: String, bottom :: String) -- = xs = ys and compute further? Possibly in this case, yes. But not in general, since there might be other data constructors also. What will occur if all the Haskell programmers set `~' before each data constructor in each pattern in their existing programs? Things won't work as you'd expect. For example, if you defined null :: [a] - Bool null list = case list of ~(x:xs) - False ~[] - True you would find that (null []) is False, not True, because the first pattern matches irrefutably. Pattern matching needs to be strict so that case statements like this work sensibly. As the types are recognized before the computation, the programs will remain safe and will become considerably faster. For example, the above program of g1 becomes a billion times faster. I wonder. Actually using irrefutable patterns tends to make a program slower, not faster, because it makes the program less strict. Good questions! -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OO idioms redux
John Goerzen wrote:
I'm not sure I understand what you mean by containment and delegation
-- could you elaborate?
This means that instead of inheriting all the member functions of the
base class and selectively overriding them, you store an object of the
base class as a member of the derived class, and make use of it in
your implementation. The standard C++ ColoredPoint example looks like
this if you use interface inheritance:
class ColoredPoint : public Point {
int color;
public:
// ColoredPoint-specific methods
};
and like this if you use CD:
class ColoredPoint {
Point p; // containment
int color;
public:
int getX() { return p.getX(); }// delegation
void setX(int x) { p.setX(x); }
// ...
// ColoredPoint-specific methods
};
If you want to take advantage of inheritance polymorphism with this
scheme, then you create an interface IPoint with virtual methods like
getX and setX, and have both Point and ColoredPoint implement it (by
inheriting it, in C++).
2. Try revisiting the original problem and thinking about how to
solve it in a Haskellish way, rather than solving it in another
language and then translating.
Thats exactly what I'm trying to do here :-) I've thought of having a
type that basically stores a bunch of functions -- an implementation
would simply provide an instance of that type with the functions,
maybe.
Yes, this is often a good approach, especially when you combine it with
labelled constructor fields.
-- Ben
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: OCaml list sees abysmalLanguage Shootoutresults
On Fri, 8 Oct 2004, Marcin 'Qrczak' Kowalczyk wrote: If the representation of some lists was changed, it would complicate all code which works on lists. Or maybe only polymorphic code, but it's still much. I don't believe it would be practical. That's true in OCaml but not in the STG-machine, where heap objects are accessed through a method-call interface. Adding new representations is easy because the caller doesn't know what the representation is anyway. GHC already uses a special packed representation for static Strings, and I see no reason why the garbage collector couldn't in principle compact lists as it copied them. I don't even see any reason why there couldn't be a packing-aware (++), or a listGetBuf :: [a] - Int - (Array Int a, [a]) which noticed when a list was packed and used memcpy() as appropriate. None of these optimizations would complicate or slow down other code which used lists, though they would complicate the run-time system of course. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stream processors
Peter Simons wrote:
type Buffer = (Ptr Word8, Int)
data StreamProc ctx a
= SP
{ start :: IO ctx
, feed :: ctx - Buffer - IO ctx
, commit :: ctx - IO a
}
Must contexts be used in a single-threaded manner? If so, I would expect
this interface:
start :: IO ctx
feed :: ctx - Buffer - IO ()
commit :: ctx - IO a
If not, I would expect this interface:
start :: ctx
feed :: ctx - Buffer - IO ctx
commit :: ctx - a
Additionally, I don't think (Ptr Word8, Int) is general enough for all reasonable uses
of this interface. For example, there's nothing inherently unsafe about calculating
the MD5 hash of the contents of an STUArray or UArray:
feedBuffer :: ctx - Buffer - IO ctx
feedSTUArray :: ctx - STUArray s Int Word8 - ST s ctx
feedUArray :: ctx - UArray Int Word8 - ctx
And what about a subrange of an STUArray or UArray? These are the problems I ran into
when trying to produce a useful MD5 library for Haskell. I feel the same way as you --
that there should be a standard way of doing this -- but I don't think the three
functions you propose are nearly enough.
-- Ben
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Stream processors
Peter Simons wrote: Ben Rudiak-Gould writes: Must contexts be used in a single-threaded manner? If so, I would expect this interface: start :: IO ctx feed :: ctx - Buffer - IO () commit :: ctx - IO a 'feed' cannot have this signature because it needs to update the context. Sure it can -- it's just like writeIORef :: IORef a - a - IO (). If the return of writeIORef were IO (IORef a) instead, it would be confusing: does it return the same IORef or a different one? If a different one, does the original one remain unchanged? If the same one, why bother returning it when the caller already had it? That's what confused me about your proposed interface. If not, I would expect this interface: start :: ctx feed :: ctx - Buffer - IO ctx commit :: ctx - a Both 'start' and 'commit' need to be in the IO monad, because creating and finalizing the context may involve IO calls. (Just think of a computation that does internal buffering in memory which is accessed through another Ptr.) In this interface contexts are supposed to be immutable Haskell values, so there's no meaning in creating new ones or finalizing old ones. The initial empty context is just a value, and the final MD5 hash (or whatever) is a pure function of the final context. Yes, this would likely involve internal use of unsafePerformIO in the implementation, but that's what it's there for (a required part of the FFI). Dealing with reuse of state might also make the library too inefficient in practice, which would be a bigger problem. feedBuffer :: ctx - Buffer - IO ctx feedSTUArray :: ctx - STUArray s Int Word8 - ST s ctx feedUArray :: ctx - UArray Int Word8 - ctx I would implement feedSTUArray and friends as wrappers around the Ptr interface, not as primitive computations of the stream processor. I think it's impossible to do this safely, but it would be great if I were wrong. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] hugs segmentation fault
Jon Fairbairn wrote: In ghci you get: [1*** Exception: loop which is better. Not much better, though: in my experience this particular exception leaves ghci in a very peculiar state, and it's usually necessary to quit and restart it before it will work again. Is it coincidence that both Hugs and GHCi have trouble handling dependency loops, or is it a very difficult problem that both have given up on solving? -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] hugs segmentation fault
Jon Fairbairn wrote: On 2004-10-29 at 00:03BST Ben Rudiak-Gould wrote: Not much better, though: in my experience this particular exception leaves ghci in a very peculiar state, and it's usually necessary to quit and restart it before it will work again. I don't think I've seen such a problem (maybe I so rarely make that type of mistake?;-). What version? What are the symptoms of this not working of which you speak? It seems OK in ghci 6.2.1 Well, here's a sample session I recorded just now: C:\\ghc\ghc-6.2.1\bin\ghci ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.2.1, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base ... linking ... done. Prelude let p = 1 : [2 * x | x - p, x 1] in p [1*** Exception: loop Prelude 123 Fail: thread blocked indefinitely C:\ Does this only happen to me? -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Set of reals...?
MR K P SCHUPKE wrote: | otherwise = contractSet (contract x0 y0:xs) ys I think you'll find the original is correct. The first two cases deal with non-overlapping ranges. The only remaining case is overlapping ranges, (partial and full overlap) both these cases are dealt with by contract, and as a result use up both the ranges at the head of both lists, sdo the merged range is prepended to the output list and the tail is calculated by passing the unused tails of both lists to contactSet... Consider the case of merging [(1,2),(3,4)] and [(1,4)]. I think your function will produce an answer of [(1,4),(3,4)]. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Set of reals...?
Keith Wansbrough wrote: Which brings me to a question: is there a better way to write -inf and +inf in Haskell than -1/0 and 1/0? Shouldn't (minBound :: Double) and (maxBound :: Double) work? They don't, but shouldn't they? -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie Question on type constructors
Brian Beckman wrote: data Shape = Circle Float | Square Float I read this something along the lines of 'Shape' is a type constructor, for use in other type-defining expressions, and 'Circle' and 'Sqare' are its two data constructors, which should be used like functions of type 'Float - Shape'. Indeed, typing Circle at the Hugs prompt reveals that Haskell has a function named Circle with type Float - Shape. However, I don't know of other circumstances where (1) I can declare functions with capitalized names (Hugs groans about syntax errors if I attempt the following: Circle2 :: Float - Shape Circle2 = Circle And (2) where the argument-types of a function can be declared on the function's right-hand side. I remember being confused in a similar way by data constructors when I learned Haskell. You might find it easier to think of Circle and Square as part of the name of a value. Circle 1.2 is one of the values in the type Shape, for example; it's not a function call which returns the value, it just *is* the value. Circle by itself doesn't really mean anything -- it's not a value of any type -- and Haskell could have been designed to make it a syntax error. But for convenience Haskell's designers decided to treat it as though it meant (\x - Circle x). -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie Question on type constructors
Paul Hudak wrote: Oh, I disagree with this point of view. Circle is certainly a value, i.e. a full-fledged function, as Brian Beckman correctly surmised. Interesting. I don't claim that my viewpoint is the One True Path, but I don't think it's wrong, either. I know you're interested in the teaching of Haskell, and the fact remains that I *was* confused by data constructors when I learned Haskell, and it *did* help me to stop thinking of them as functions. Different people learn in different ways, and that's how I learned; even now I find this view more natural than the view of constructors as functions. The wording of the OP's article made me think that he might be suffering from the same conceptual problem, so I tried to suggest the approach which worked for me. The Haskell designers did not decide for convenience that Circle is the same as \x - Circle x. Rather, that's a fundamental law (the eta law, to be exact) of the lambda calculus, on which Haskell is based. I think you're begging the question here -- the eta law applies to functions -- but maybe you're just elaborating on your view rather than arguing for it, as I was. (I.e. I was elaborating, not arguing, when I said that Circle was a function for convenience.) The real reason that the Haskell designers chose to have constructors begin with a capital letter is to make pattern-matching clearer. Certainly it's odd to be able to match on the result of a function. case factorial (2*3) of factorial n - ... won't work, so it's surprising that case Circle (2*3) of Circle x - ... does, if Circle is a function. On the other hand, if Circle 6 is just a literal value, it's not at all surprising that case Circle 6 of Circle x - ... does what it does. And, at least for me, that extends to case Circle (2*3) of Circle x - ... as well. (*) is being called in this example, and is returning an entirely new value, 6, but Circle is just getting added on to that result, and then stripped off again. There's a clear symmetry between construction and deconstruction which doesn't seem nearly as clear if Circle is seen as a function. It occurs to me that when I talk about functions here, I am talking about Haskell function values, not about functions as equations f(x) = In particular, one cannot write an invert :: (a-b) - Maybe (b-a) which never returns a wrong answer, except for invert = const Nothing -- this is why it makes no sense to me to imagine Circle as being a Haskell *value*. I have no problem imagining it as a function in a more abstract mathematical sense; it's just that Haskell function values don't have that extra structure. The view of Circle that I was trying to express is closer to Prolog clauses. One can assert circle(1.2), and that assertion will match circle(x), but it doesn't really make sense to assert circle, or to try to match it. Have I succeeded in reconciling our views? -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie Question on type constructors
Keith Wansbrough wrote: Indeed, they are functions. Another way of thinking about it is as an initial algebra (technical term). What this means is this: Shape is a set of values that contains - the result of Circle x for all values x :: Float - the result of Square x for all values x :: Float such that - there's nothing in Shape that can't be reached this way (no junk) - there is no value in Shape that can be reached in two different ways (no confusion). I think this is orthogonal to the point of contention. For all x :: Float, what value results when your function Circle is applied to the argument x? Obviously, my value Circle x. So the function Circle can be eliminated from the definition by inlining, yielding Shape is a set of values that contains - the value Circle x for all values x :: Float - the value Square x for all values x :: Float such that [...] This is exactly how I would define Shape. (Well, not quite -- there *are* values in Shape that can't be constructed this way, but that's a totally different issue.) -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie Question on type constructors
Paul Hudak wrote:
Ben Rudiak-Gould wrote:
Have I succeeded in reconciling our views?
Perhaps! In particular, perhaps it's just a pedagogical issue.
I'm interested in it mainly from a pedagogical perspective, yes.
Note that instead of:
data Shape = Circle Float
| Square Float
the Haskell designers might have used the following syntax:
data Shape where
Circle :: Float - Shape
Square :: Float - Shape
which conveys exactly the same information, and makes it quite clear
that Circle and Square are functions.
No, this is totally different from what I'm talking about. My position
for the moment is that they *aren't* functions (or, more precisely, that
they shouldn't be so taught), and anything that tries to further the
illusion that they are is then a step in the wrong direction.
In particular, your notation with type signatures makes it totally
unclear that Circle and Square have disjoint ranges; in fact it looks
like they have the same range. This notation would have increased my
confusion when I was still learning, because what I didn't understand at
that time was the nature of the type Shape. Saying that Circle and
Square are functions which take a Float and return a Shape tells me
nothing about what a Shape is; it might as well be an abstract data
type. What I needed to know, and was never clearly told, was that Shape
is *precisely the following set:* { Circle 1.2, Circle 9.3, ..., Square
1.2, Square 9.3, ...}. You could even throw in a _|_ and some
exceptions-as-values, though I'm not sure it would have been advisable
(little white lies are an important pedagogical tool, as long as you
eventually own up).
The syntax that would have made the most sense to me would have been
something like
data Shape =
forall x::Float. Circle x
forall x::Float. Square x
with maybe a + or something joining the lines, though that might have
done more harm than good.
Of course GHC 6.4 has your function syntax now with the introduction of
GADTs, but I think that it's a mistake; in fact it's interfering right
now with my attempt to understand what GADTs are! I suppose I would prefer
data Term a =
forall x :: Int. Lit x :: Term Int
forall x :: Term Int.Succ x :: Term Int
forall x :: Term Int.IsZero x :: Term Bool
forall x :: Term Bool.
forall y,z :: Term a. If x y z :: Term a
In fact, maybe I'll try rewriting everything in this form and see if it
helps me. I suppose once I do understand GADTs I'll have a better idea
of what would have helped.
As for pattern matching, I think the key point relates to Keith
Wansbrough's comment that an algebraic data type denotes an initial
algebra. If you want to retain referential transparency, each
application of the function being pattern-matchined against must yield
a unique value (i.e. no confusion as Keith describes it). This is
guaranteed with a constructor, but not with arbitrary functions. So,
another way to look at it is that constructors simply carve out a
portion of the function space where this can be guaranteed.
I have no objection to this viewpoint except that I fear it's too
abstract for students. I can understand it because I already understand
algebraic data types, but I don't think it would have helped me learn.
That said, there are lots of interesting directions to pursue where
pattern-matching against functions IS allowed (requiring higher-order
unification and the like). I suppose that topic is out of the scope
of this discussion.
I don't think I've heard of this (unless you're talking about logic
programming). Can you point me to some papers?
-- Ben
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie Question on type constructors
Benjamin Franksen wrote: Because, hmmm, isn't it rather *one* destructor with type destructShape :: Shape - (Double - t) - (Double - t) - t where the second and third arguments explain what to do with a Circle resp. a Square? So that case s of Circle r - f r Square l - g l is another way to write destructShape s g f I can't resist pointing out that we don't even need destructShape, nor any internal representation of a Shape, because we can make the value itself the deconstructor: Circle :: Double - (Double - t) - (Double - t) - t Circle d = \c s - c d Square :: Double - (Double - t) - (Double - t) - t Square d = \c s - s d Every algebraic data type has a natural representation of this form. I used this idiom extensively in my Lazy K sample code [1] [2]. -- Ben [1] http://homepages.cwi.nl/~tromp/cl/lazy-k.html [2] http://esoteric.sange.fi/essie2/download/lazy-k/eg/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Double - CDouble, realToFrac doesn't work
Henning Thielemann wrote: I wonder why Infinity has a sign in IEEE floating processing, as well as 0. To support this behaviour uniformly one would need a +0 or -0 offset for each number, which would lead straightforward to non-standard analysis ... See Branch Cuts for Complex Elementary Functions, or Much Ado About Nothing's Sign Bit by William Kahan, in The State of the Art in Numerical Analysis, (eds. Iserles and Powell), Clarendon Press, Oxford, 1987. (Note that I have not read this paper. However, Kahan was the primary architect of the IEEE floating point standard, so you can be pretty sure the reasons given in the paper are also the reasons IEEE floating point has signed zero.) A good online presentation which mentions all kinds of interesting floating point pathologies, including those discussed in the above paper, is How Javas Floating-Point Hurts Everyone Everywhere (http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf). [...] Thus (a-b) is not the same as -(b-a) for IEEE floats! Nor is x*0 equal to 0 for every x; nor does x == y imply f(x) == f(y) for every x, y, f; nor is addition or multiplication associative. There aren't many identities that do hold of floating point numbers. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Global Variables and IO initializers
I think the broad issue is that there are many different levels of the system at which something can be global: a module, a thread, a process, a user, a computer, a network segment, the internet, the universe, etc.. If your model of a concept is more global than the concept itself, you lose flexibility. If your model is less global than the concept, you get cache-coherency problems. The global variables we're talking about here are global to a single invocation of a Haskell program [*] [**]. The only concepts which are appropriately modeled by such globals are those whose natural scope is a single invocation of a Haskell program. Are there any? Adrian Hey's example of a badly-written C library is one. But I agree with Robert Dockins that such cases are better solved in C than in Haskell. (stdin,stdout,stderr) seem to naturally have this scope (assuming you don't use freopen). There needs to be only one Handle created for each of these because otherwise the buffering won't work properly. Global - initializers seem like the right thing here. Are there any others? -- Ben [*] Adrian Hey has argued that global variables aren't really global. I think he's talking about hiding them through module scoping. What I mean by global is different: something is global at a particular level of the system if there's only one instance of it at that level. [**] Wouldn't it make sense to support thread-local global state also, if we're going to support process-local global state? ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] One-shot? (was: Global variables and stuff)
Graham Klyne wrote: Wouldn't it be easier to simply define once as a common Haskell library function? Depends on the type and the expected semantics. As Adrian Hey already pointed out, (once :: IO a - IO a) with the obvious semantics is never going to be safe, because it's just not the case that x = once (newIORef ()) y = x has the same intended meaning as x = once (newIORef ()) y = once (newIORef ()) No amount of compiler-specific magic is going to fix this. On the other hand, these are perfectly safe: once' :: IO a - IO (IO a) oncePerString :: String - IO a - IO a oncePerType :: Typeable a = IO a - IO a once' seems virtually useless unless you have top-level -, but the other two don't need it. I'm not sure which would be preferable. I lean toward oncePerString as more flexible and predictable, though it requires a certain discipline on the part of its users. In any case there would need to be support for different scopes: perProcess :: String - IO a - IO a perThread :: String - IO a - IO a perMachine :: String - IO a - IO a I suppose you could add perType :: Typeable a = IO a - IO a with the stipulation that types in different processes are distinct (which seems like the only safe assumption). -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] IO and State
Iavor S. Diatchki wrote:
In GHC the whole program stops when the main thread exits.
So if the law I was talking about holds, this program should
never terminate, as it will forever loop in 'reader'.
However since there is a concurrent thread running that can modify
the state, if 'reader' is interrupted between the two readSTRefs
we will get different values for 'x' and 'y' and 'reader' will stop.
I tried that in GHC and it stops after a little while, so the law does
not hold.
I would say that the law holds in one direction and not the other. It's
safe to replace
do x - readSTRef r
y - readSTRef r
with
do x - readSTRef r
let y = x
but not the other way around. The semantics for concurrency don't
guarantee that a task switch will /never/ happen between two calls of
readIORef, but they don't guarantee that a task switch will /ever/
happen, either, so relying on your sample application terminating is
non-portable. Therefore optimizing it in such a way that it never
terminates is safe.
If it's important to distinguish ST actions which can be treated as IO
from others which can't, you can introduce a type class
class PrivateState s where {}
and a new function
newPureSTRef :: forall a s. PrivateState s = a - ST s (Ref s a)
newPureSTRef = newRef
There don't need to be any instances of PrivateState; the only important
thing is that RealWorld isn't an instance. Any code which uses a Ref
created by newPureSTRef is restricted to the PrivateState space and
therefore can't be used as part of an IO action. runST would be given
the more general type
runST :: forall a. (forall s. PrivateState s = ST s a) - a
which would work for pure ST and ordinary (IO-embeddable) ST actions.
stToIO would retain its current type, and so would not work with pure ST
actions. Your equivalence would apply in both directions to any action
of type (forall s. PrivateState s = ST s a).
I don't think this careful approach is necessary in practice, but I hope
the fact that it can be done [*] makes the merging of ST and IO look
more reasonable.
-- Ben
[*] Except how would you prevent the user from declaring an instance for
PrivateState RealWorld? Oh well. It can be done /in principle/. :-)
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Space efficiency problem
Adrian Victor CRISCIU wrote: Thanks for the advice. However, though I don't know how ghc manages the heap, I am not sure it is possible to achieve constant heap usage, because a value of type State is a function, and = is creating a call stack in this case. I mean, I think that, even if the argument of f :: a - State s a has a stricness flag, the value m0 :: State s a is itself a function of the state (with type s); then the value ((m0 = f) = f) = .) = f is applied to a state s0, this must be passed down to the bottom of the call stack to perform the actual computation. And this may eat up a lot of heap space. I don't think this is a problem if the expression associates the other way (as your program does), i.e. m0 = (\x - f x = (\x - f x = (\x - f x = ... f))) This can be tail recursive if there's enough strictness. On a related note, it seems like it might be worth introducing (==) :: Monad m = (a - m b) - (b - m c) - a - m c with a higher precedence than (=) and associating to the right, so that one could write m0 = f1 == f2 == ... == fn and avoid the inefficiency of the left-associative (=). Does this make any sense? -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] IO and State
Iavor S. Diatchki wrote: Ben Rudiak-Gould wrote: I would say that the law holds in one direction and not the other. [...] How can things be equal the one way and not the other? Saying that two things are equal means (in this context) that either can be replaced by the other without changing the semantics. In other words, the first can be replaced by the second without changing the semantics, and the second can be replaced by the first without changing the semantics. One of those replacements is valid and the other invalid (I argue). Of course it follows that the two things are not equal -- i.e. I agree with you. :-) The semantics for concurrency don't guarantee that a task switch will /never/ happen between two calls of readIORef, but they don't guarantee that a task switch will /ever/ happen, either, so relying on your sample application terminating is non-portable. Therefore optimizing it in such a way that it never terminates is safe. My example had nothing to do with non-termination. Nor did my response. I could change the ending to: [...] so relying on (x == y) ever being False is non-portable. Therefore optimizing it in such a way that it is never False is safe. It illustrated that with the one piece of code, a boolean value in the program will be always True, while with the other it could become False [...] Right, in the first piece of code the expression is guaranteed to be True, while in the second there are no guarantees -- the value could be True or False each time. Therefore it's safe to transform the second expression into the first during optimization, because always True is a special case of anything at all. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Pure Haskell Printf
Keean Schupke wrote: At the risk of getting off topic... the reason 'C' has printf is because it is not polymorphic. Printf is a hack to allow different types to be printed out, such that they did not need printInt, printFloat etc. Many language have printf-like functions despite not satisfying this criterion. Perl, Python, and Common Lisp are the three that come to mind. I think the reason they have it is that it's useful in general to be able to visually separate the string template from the expressions being printed. Even (name++, your age is++age++.) is pretty punctuation-heavy for a template. (Plus, it has a bug in it, which would be much easier to see in the printf syntax.) -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Global Variables and IO initializers
Benjamin Franksen wrote: label1 = unique Uniq1 label2 = unique Uniq2 global1 = functionalNewMVar label1 True global2 = functionalNewMVar label1 (117::Int) No dice. Your example inadvertently shows why: you used label1 when creating both global1 and global2, and now I can write coerce :: Bool - Int coerce x = putMVar global1 x takeMVar global2 (provided I've emptied them first). -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Global Variables and IO initializers
Benjamin Franksen wrote: My god, what a stupid mistake. I should just give it up... :-( Funny you should say that, because I made the same mistake two weeks ago and felt the same way: http://www.haskell.org/pipermail/haskell-cafe/2004-November/007556.html Live and learn... -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: not possible with monad transformers ?
Jules Bean wrote: However, your problem *does* have a natural underlying monad, if you care to use it. I may be confused, but I don't think it does. It seems like the OP wants a type like data Perhaps a = Success a | Failure [Error] and semantics like liftM2 (+) (Failure [error1]) (Failure [error2]) === Failure [error1,error2] where liftM2 f a1 a2 = a1 = p where p v1 = a2 = q where q v2 = return (f v1 v2) I don't see how to define (=) such that this will return the appropriate value. If a1 fails you must call p in order to collect additional errors, but there's no appropriate value of v1 that you can pass. But it's easy with a custom lifting function: liftPerhaps2 f (Success x) (Success y) = Success (f x y) liftPerhaps2 f p q = Failure (errors p ++ errors q) where errors (Success _) = [] errors (Failure es) = es -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Top-level state debate on the wiki
I put up a wiki page summarizing the main proposals for top-level mutable state. The type-dictionary approach isn't there yet, but there's a space for it; I'll probably fill it in within the next 24 hours unless someone else feels like doing it first. Please add more detail, objections, examples. Especially examples! Here's the page: http://haskell.org/hawiki/GlobalMutableState (It also includes an explanation of why I chose that title, though of course you're welcome to dispute that too.) -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Top-level state debate on the wiki
Keean Schupke wrote: Ben Rudiak-Gould wrote: [...] Just a small comment on the Wiki page... it says Several real-life examples of pure haskell code which needs fast global variables to either be implemented efficiently or statically guarantee their invariants are given in http://www.haskell.org//pipermail/haskell/2004-November/014929.html; I don't know if this post was meant specifically for me, but in any case I didn't write the sentence quoted above. Other people have already added material to my original wiki page, and I encourage you to do the same if you disagree with what's there right now. To everyone who's posted in this thread: I think you're misunderstanding what I meant by the phrase on the wiki. :-) My hope was/is that this whole debate /moves/ to the wiki exclusively. My impression is that the mailing-list debate has made no progress for some time (weeks) and almost all of the traffic now consists of weekly or daily repetitions of the same old points and counterpoints. This is a sign that the time has come to move to a discussion format that doesn't require reiteration. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mutable data design question
GoldPython wrote: In the case of writing something like a text editor where the data involved is by its very nature mutable, what sort of design paradigm would you use in a functional language? I wouldn't say that textual data is by its nature mutable. That's just the imperative way of looking at it. The functional way is to think of all possible documents as Platonic entities -- the books in Borges's library -- and of writing a document as the process of choosing which book you want. When you insert or delete a character you're moving your attention from one book to a nearby one. The problem then is finding a way of representing books as values in your program in such a way that nearby books, in the above sense, have similar values that can take advantage of sharing. The typical approach is to describe each book inductively as the concatenation of several smaller ones, bottoming out at short phrases (say). Then when you add or delete a character, only one sub-book has changed, and in that sub-book only one sub-sub-book has changed, and so on, so you only need to replace one index at each level, which costs a logarithmic amount of work. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Force evaluation
Michael Walter wrote: PS: Ooops, posted this to haskell-ml first. Actually I think your question is more appropriate to haskell than to haskell-cafe. If it balloons into a huge discussion then it can move here. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Non-technical Haskell question
[EMAIL PROTECTED] wrote: When I use javac every file that is created is necessary for the application to run. This can't be said of the ghc compiler. Having an excuse that this is way the C compiler does it or that this is the way its always been done is to poor of a reason to even argue against. If a file isn't needed then it shouldn't be left there. [...] Does this bother me? Not in particular, its just an indication that this is an old design. As Mark Carroll said, the .o and .hi files are there to support separate compilation. GHC supports separate compilation because it's useful. Believe me, Haskell is the last language to do something just because everyone else does it. :-) The javac approach isn't better, just different. If the next version of GHC could produce portable bytecode files, that would be a good thing (except that it would make GHC even more complicated than it already is). If the next version of GHC could *only* produce portable bytecode files, that would be a bad thing, since it would lose functionality (while gaining other functionality). Your newer-is-better premise makes little sense. Haskell is a far newer language than Java; many aspects of Haskell's design are no older than Haskell, while nearly all aspects of Java's design have been around in other languages for decades. You might as well be arguing that Java is better because it's based on older, proven technology. Better yet, suppress the urge to compare Haskell and Java at all; after all, the more different they are, the more worthwhile it is to learn both! Once you're reasonably adept at programming in different languages, then you can start thinking about ways to combine the advantages of each. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Non-technical Haskell question
Philippa Cowderoy wrote: The strip utility helps somewhat, I just dropped a wxHaskell app from a 10 meg .exe to about 3.6 megs under windows. You can also compress the stripped executable with UPX. GHC-generated executables seem to compress very well (about 4:1 in my experience), and even a very large executable, like GHC itself, decompresses so quickly that I can hardly tell the difference in startup time. Caveat: this actually increases virtual memory requirements, since the executable image in memory can't be backed by the executable file on disk. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Non-technical Haskell question
John Goerzen wrote: On Tue, Dec 07, 2004 at 12:43:27PM +0100, Lennart Augustsson wrote: Yay! :) Dynamically linked libraries are slower than statically linked ones in just about every implementation I know of. I don't care. My understanding was that this was mostly limited to x86 platforms. From memory, an additional register is consumed when using dynamic libraries on that platform, and due to its already limited number of registers, that can mean a hit. I'm not sure what this would be unless it's the frame pointer (ebp). I don't know of any reason you can't omit the frame pointer in dynamically linked applications, though, unless one of the DLLs you're linking with wants to unwind your stack, in which case you'd have the same problem linking statically. Dynamic linking has other costs. If the library is relocated, you have to use a jump table (slows down every call) or patch all calls directly (interferes with demand paging). Code cache locality is reduced because the linker can't discard unused library functions. And there are problems with inlining. :-) -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flattening tail recursion?
GoldPython wrote: I know there's length to count the elements in a list and it works fine, but the function below stack overflows on a large list. countLines [] = 0 countLines (_:ls) = 1 + countLines ls I would have thought that this was tail recursive and would be flattened into iteration by the compiler. This is not tail recursive as written. SICP section 1.2.1 does a good job of explaining how to tell the difference: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 The analysis in Haskell is a bit different in general because reductions are applied in a different order, but in this case it's exactly the same. Some compilers might indeed optimize your code into a tail-recursive version, but there's a catch: the optimization depends on the commutativity and associativity of (+), which doesn't hold for arbitrary types in Num. Try giving countLines an explicit type signature like ([a] - Int) and see if that helps. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flattening tail recursion?
Jules Bean wrote: On 10 Dec 2004, at 15:34, Robert Dockins wrote: So it should get flattened, but it still doesn't run in constant space because the x parmeter isn't strict, so it will accumulate a bunch of closures like (((0)+1)+1)+1)+1)+1) To make it strict, do something like this: Isn't this what the strictness analyser is for? Doesn't GHC know that + for Int is strict in both arguments, and therefore it shouldn't accumulate a great big thunk like that? It doesn't know that about (+) :: Num a = a - a - a. The original poster's code didn't mention Int anywhere, so GHC probably had to assume the worst. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flattening tail recursion?
Georg Martius wrote: It was allready posted before, that you need to enforce the evaluation of the + in order to get the function run in constant space. The thing is, that it is harder to achieve than I expected it to be. countLines' ls = foldl (\x y - let x' = x + 1 in x' `seq` y `seq` x' ) 0 ls will run in constant space, but just if compiled with -O (ghc-6.2.1). The seq function forces the evaluation of its first argument (at least to Head Normal Form). The second one is just passed through. This isn't quite right. It's more accurate to say that seq ties together the evaluation of its arguments, so that the left argument is evaluated whenever (and just before) the right argument is. In particular, (x `seq` x) is the same as x. Your expression let x' = x + 1 in x' `seq` y `seq` x' evaluates x' redundantly; it's (almost) semantically equivalent to let x' = x + 1 in y `seq` x' which is equivalent to y `seq` (x + 1) which, in this instance, might as well just be x + 1 since the strictness problem is unrelated to the list elements passed in y. In fact there's nothing you can do inside either argument to foldl to make the accumulation strict, because the arguments aren't used until the whole list has already been processed and the huge intermediate thunk has already been built. You need a separate strict foldl function, usually called foldl', which was unaccountably omitted from the prelude. If GHC does manage to compile a use of foldl into strict code, it's because of its internal strictness analyzer, not because of any explicit calls to seq. Because I'm a cautious guy, I actually tried compiling both versions with ghc -O to check that I was right -- and I'm wrong! GHC does treat them differently. It even treats countLines' ls = foldl (\x y - let x' = x + 1 in x' `seq` y `seq` x' ) 0 ls differently from countLines' ls = foldl (\x y - let x' = x + 1 in y `seq` x' ) 0 ls The latter overflows the stack, the former doesn't. I have no idea what's going on here. Simon PJ? Simon M? -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The difference between ($) and application
Derek Elkins wrote: Andrew Pimlott wrote: I think this post should go under the heading ($) considered harmful. I've been bitten by this, and I never use ($) anymore in place of parentheses because it's too tempting to think of it as syntax. I find this position ridiculous. [...] If you ever make a mistake one way the type checker will tell you. For what it's worth, this is not true in the presence of implicit parameters: f :: ((?p :: Int) = Int) - Int f g = let ?p = 1 in g x,y :: Int x = let ?p = 2 in (f ?p) == 1 y = let ?p = 2 in (f $ ?p) == 2 I wouldn't mind ($) being magical, along the lines of the magical runST in a rank-1 type system. It would be nice to be able to use it in patterns too. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Seeking comments on this IO proposal
John Goerzen wrote: My proposal is here: http://www.complete.org/~jgoerzen/t/MissingH.IO.HVIO.html I'm aware that others have been working on IO proposals; specifically, Simon Marlow's here: http://www.haskell.org/~simonmar/io/System.IO.html The proposal on Simon M's page was originally my design, though Simon made many improvements. You can read my rationale for the original design in these mailing-list messages: http://www.haskell.org/pipermail/haskell/2003-July/012312.html http://www.haskell.org/pipermail/libraries/2003-July/001255.html http://www.haskell.org/pipermail/libraries/2003-July/001257.html http://www.haskell.org/pipermail/libraries/2003-July/001273.html http://www.haskell.org/pipermail/libraries/2003-August/001319.html http://www.haskell.org/pipermail/libraries/2003-August/001336.html http://www.haskell.org/pipermail/libraries/2003-August/001366.html I had to abandon many of the original ideas because the Posix and Win32 APIs can't support them. (Some examples of things you should be able to do, but can't in Posix or Win32: given a directory handle and the name of a file in the directory, open that file; given a file handle with read access, acquire write access if available; conduct atomic filesystem transactions.) The most important idea that survives is the separation of files from input streams and output streams, Given this background you can probably guess that I'm not too keen on the traditional open/read/write/seek/close model; I don't think it's a good abstraction for anything, even files. I love the idea of gzip and gunzip as transformations on streams, though, and streams backed by memory buffers appear in my proposal too. * Would I be better advised to try to implement some existing ideas instead? Yes, you should definitely spend your time implementing my pet idea, not yours. :-) * Are there any other implementations of these things that are ready to use? (With code) Simon wrote a prototype implementation of his/my proposal: http://www.mail-archive.com/haskell-cafe@haskell.org/msg05138.html -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parse text difficulty
Henning Thielemann wrote:
I try to stay away from list comprehension because I can't memorize in
which order the conditions are processed [...]
I remember it as being slowest-changing-to-the-left, just like the
positional notation for integers. E.g.
[[x,y] | x - ['1'..'4'], y - ['0'..'9']]
will give you the numbers from 10 to 49 in order (as strings).
Another way to remember is that it's the same order as its equivalent
using the list monad:
do { x - ['1'..'4']; y - ['0'..'9']; return [x,y] }
-- Ben
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] FFI woes!
Sebastian Sylvan wrote: If there was a way to simply defer GC (like you attatch a function to an object which can simply deny the GC the right to remove it depending on its state) then I wouldn't have to do anything significant in the finalizer. Why not spawn a thread which starts the playback, waits for it to finish, and then exits, and wrap the whole thread in a call to withForeignPtr? Then your finalizer won't be called prematurely. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] FFI woes!
Sebastian Sylvan wrote: Ben Rudiak-Gould wrote: Why not spawn a thread which starts the playback, waits for it to finish, and then exits, and wrap the whole thread in a call to withForeignPtr? Then your finalizer won't be called prematurely. Well I could do this, but for one it would be cumbersome to stop playback. I don't think it is. Let me try to specify the problem precisely to make sure we're talking about the same thing. We have an interface something like this: loadSong :: String - IO (Ptr SongRep) playSong :: Ptr SongRep - IO () stopPlaying :: Ptr SongRep - IO () -- it will also stop by itself isPlaying :: Ptr SongRep - IO Bool freeSong :: Ptr SongRep - IO () -- unsafe if song is playing and we want an interface like this: loadSong' :: String - IO Song playSong' :: Song - IO () stopPlaying' :: Song - IO () isPlaying' :: Song - IO Bool I think this implementation will work: type Song = ForeignPtr SongRep loadSong' name = loadSong name = newForeignPtr freeSong playSong' song = forkIO (withForeignPtr song (\s - playSong s waitForSilence s)) waitForSilence s = do threadDelay 50 b - isPlaying s when b (waitForSilence s) stopPlaying' song = withForeignPtr song stopPlaying isPlaying' song = withForeignPtr song isPlaying If you need the return value from playSong, this should also work: playSong' song = do rtn - withForeignPtr song playSong forkIO (withForeignPtr song waitForSilence) return rtn But this won't work, because the withForeignPtr call will return before the thread exits: brokenPlaySong' song = withForeignPtr song (\s - playSong forkIO (waitForSilence s)) -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why no IO transformer monad?
Ross Paterson wrote: But IO is not ST RealWorld (even if GHC pretends it is): other users of the world are not waiting for the new world produced by your Haskell program. They're *part* of the world. IO = State RealWorld makes sense if you think of RealWorld as encapsulating the entire state of the universe, including other users. The only trouble is that concurrent processes end up containing each other. I'm not entirely convinced that this can't be solved with some sort of fixed-point trick. -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hugs vs GHC (again) was: Re: Some randomnewbiequestions
Andre Pang wrote: Is there a Wiki page or URL with the steram proposal? It's here: http://www.haskell.org/~simonmar/io/System.IO.html -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hugs vs GHC (again) was: Re: Some randomnewbiequestions
Marcin 'Qrczak' Kowalczyk wrote: fileRead :: File - FileOffset - Integer - Buffer - IO () This is unimplementable safely if the descriptor is read concurrently by different processes. The current position is shared. ... which is terrible library design, which we should avoid if at all possible, which is one of several reasons that I want to get rid of the notion of current position. Hence the above prototype. fileRead can be implemented in terms of OS primitives, and it's easy enough to implement a thread-safe seek/read interface on top of it. The reverse isn't true--if we provided seek/read, it would be very hard to implement fileRead safely. (Maybe that's what you were saying?) -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: I/O interface
Marcin 'Qrczak' Kowalczyk wrote: Ben Rudiak-Gould [EMAIL PROTECTED] writes: fileRead can be implemented in terms of OS primitives, Only if they already support reading from a fixed offset (like pread). I'm not sure if we can rely on something like this being always available, or whether it should be emulated using lseek which is safe only as long as we are the only process using the given open file. First of all, I don't think any OS shares file pointers between processes. Otherwise it would be practically impossible to safely use an inherited filehandle via any API. Different threads using the same filehandle do share a file pointer (which is a major nuisance in my experience, because of the lack of an atomic seek-read/write), but a Posix fork duplicates the file pointer along with all other state. I can't believe I'm wrong about this, but someone please correct me if I am. This limits the problem to a single process. If you're only using GHC's lightweight threads, there's no problem at all. If you're using OS threads, the worst thing that could happen is that you might have to protect handle access with a critical section. I don't think this would lead to a noticeable performance hit when combined with the other overhead of file read/write operations (or lazy evaluation for that matter). pread requires that the file is seekable, which means that it can't be used for all file handles: not for pipes, sockets, terminals nor various other devices. The file interface in this library is only used for files, which are always seekable (by definition). If you want to treat a file as a stream, you create an InputStream or OutputStream backed by the file. Such streams maintain internal (per-stream) file pointers. Not if it must cooperate with other processes, and you *do* want to set a file position before running another program with redirected standard I/O. In this case it's not enough that you set a private Haskell variable holding its logical file position - you must perform the lseek syscall. If you're using Posix fork/exec, you can use Posix lseek without losing portability. If you're using a higher-level Haskell library to spawn the program, it will be Stream-aware (if it supports redirection at all) and will know how to set the system file pointer when necessary. Doing something differently than everybody else has a risk of limited interoperability, even if the new way is better, and thus must be carefully evaluated to check whether all lost functionality is unimportant enough to lose. Very true. (But hardly a new problem for Haskell.) -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: I/O interface
Marcin 'Qrczak' Kowalczyk wrote: Ben Rudiak-Gould [EMAIL PROTECTED] writes: The file interface in this library is only used for files, which are always seekable (by definition). What do you mean by files? What you get from open() is not always seekable [...] This was all discussed a year ago, and rather than reiterate it I'll try to expand the wiki page when I have a chance. Maybe all of this new discussion should be on the wiki also. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: I/O interface
Simon Marlow wrote: I assumed that dup()'ing file descriptors would be enough to produce separate file pointers, but no. Question (for qrczak or the group at large): is there *any* way to get, without an exploitable race condition, two filehandles to the same file which don't share a file pointer? Is there any way to pass a filehandle as stdin to an untrusted/uncooperative child process in such a way that the child can't interfere with your attempts to (say) append to the same file? So you can only safely make a single stream from a File. I think we just need more kinds of streams. With regard to file-backed streams, there are three cases: 1. We open a file and use it in-process. 2. We open a file and share it with child processes. 3. We get a handle at process startup which happens to be a file. In case 1 there are no problems, and we should support multiple streams on such files. In case 2 we could avoid OS problems by creating a pipe and managing our end in-process. This would allow attaching child processes to arbitrary streams (e.g. one with a gzip filter on it, if we ever implement such a thing). In certain cases it might be possible to rely on OS support, but it seems fragile (if we create two child processes tied to two streams on the same file). Case 3 is the most interesting. In an ideal world I would argue for treating stdin/out/err simply as streams, but that's not practical. Failing that, if we have pread and pwrite, we should provide two versions of stdin/out/err, one of type InputStream/OutputStream and the other of type Maybe File. We can safely layer other streams on top of these files (if they exist) without interfering with the stream operation. The only thing we can't do with this interface is screw up the parent process by seeking the inherited handles. Can anyone come up with a case for allowing that in the high-level library? It can always be done through System.Posix. If we don't have pread and pwrite, we're screwed, but so is every other application on this badly broken OS. If we punt on the interference problem, we can implement a pread and pwrite that are atomic within our process, and go from there. We're no worse off than anyone else here. Unfortunately, Win9x lacks pread and pwrite. But anyone running Win9x is clearly willing to deal with much worse problems than this. Making multiple streams would require re-opening the file for each subsequent one, Windows Server 2003 has ReOpenFile, but no prior version of Win32 can do this, as far as I know. I don't know the *ix situation. With ReOpenFile we could implement a lot more of my original proposal, including a File type that really denoted a file (instead of a file access path). -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hugs vs GHC (again)was: Re: Somerandomnewbiequestions
Marcin 'Qrczak' Kowalczyk wrote: File positions are not evil. They allow to treat files and devices in a uniform way. Indeed, file positions are exactly as evil as indices into shared memory arrays, which is to say not evil at all. But suppose each shared memory array came with a shared current index, and there was no way to create additional ones. Suppose you couldn't index the array by a local variable: instead, you had to store the local variable into the shared index register first, overwriting whatever was there before. If you only wanted to use the array as a source or sink for a single stream, that would be fine. In every other case, it would be awful. Even read-only sharing would require the invention of some sort of cooperative locking discipline, and if some process didn't respect the locking and couldn't be changed, read-only sharing would become impossible. That's just silly. The way to solve this problem is to decouple the index from the shared memory array. You can easily simulate the single-index behavior if that's what you want, but you also get a lot of additional functionality. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Marcin 'Qrczak' Kowalczyk wrote: Henning Thielemann [EMAIL PROTECTED] writes: I did some shuffling based on mergesort [...] I think it doesn't guarantee equal probabilities of all permutations. It doesn't (proof: it has a bounded runtime, which can't be true of a perfect shuffling algorithm based on coin flips). But it looks pretty good. I think that iterating this algorithm n times is equivalent to assigning a random n-bit number to each list element and sorting, which is equivalent to Chris Okasaki's approach with one iteration and an array of size 2^n. Henning Thielemann [EMAIL PROTECTED] writes: It even works for infinite lists. In the sense that it doesn't diverge if you evaluate any finite prefix of the list, yes. In the sense that it does a good job of shuffling the list, no. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Scott Turner wrote: Analogous to quicksort's bad behavior in the worst case, an invocation of 'partition' is not guaranteed to make any progress with the shuffling, because one of the output lists might receive all of the input items. It's worse than quicksort, because there's no guarantee that the algorithm will ever terminate. But this is actually optimal--there's no way to perfectly shuffle a list using a bounded number of coin flips, because n! doesn't divide any power of 2 for n=3. I posted this algorithm on comp.lang.functional a while ago: http://groups-beta.google.com/group/comp.lang.functional/browse_frm/thread/570615e64e3e4fc0 -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hugs vs GHC (again)was: Re: Somerandomnewbiequestions
John Meacham wrote: Actually, If I were writing new haskell libraries, I would use mmap whenever I could for accessing files. not only does it make the file pointer problem go away, but it can be drastically more efficient. I'm not sure this is a good idea, because GHC really needs non-blocking I/O to support its thread model, and memory-mapped I/O always blocks. In fact this is a problem even if we only memory-map files at the programmer's request. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] I/O interface
Marcin 'Qrczak' Kowalczyk wrote:
Convenience. I'm worried that it uses separate types for various
kinds of streams: files, pipes, arrays (private memory), and sockets.
Haskell is statically typed and lacks subsumption. This means that
even though streams are unified by using a class, code which uses
a stream of an unknown kind must be either polymorphic or use
existential quantification.
Yes, this is a problem. In my original proposal InputStream and
OutputStream were types, but I enthusiastically embraced Simon M's idea
of turning them into classes. As you say, it's not without its
disadvantages.
I see several possibilities here.
* We could adopt Avery Lee's suggestion (from the discussion in
2003) to use field labels instead of methods. Advantages: InputStream
and OutputStream behave more like their OOP equivalents, with no loss of
extensibility. Disadvantages: potentially less efficient (no
specialization possible); loses some static type information.
* We could use a single type for all input and output streams in the
standard library, but retain the type classes also.
* We could provide existential wrappers:
data IStream = (InputStream a) = MkIStream !a
instance InputStream IStream where ...
A nice thing about the last approach is that it supports dynamic
downcasting:
case (x :: IStream) of
MkIStream x -
case (Data.Dynamic.cast x :: UArrayInputStream) of
Just x - (getUArray x, getCurrentIndex x)
Nothing - ...
Completeness. Unless File{Input,Output}Stream uses {read,write}()
rather than file{Read,Write}, openFile provides only a subset of
the functionality of open(): it works only with seekable files,
e.g. not with /dev/tty.
What is the type of stdin/stdout? They may be devices or pipes
(not seekable), regular files (seekable), sockets...
Simon M's current interface is incomplete, but the concept is fine.
Again, to try to avoid confusion, what you call a seekable file the
library calls a file, and what you call a file I would call a Posix
filehandle. Roughly. It's hard to be precise because file is such a
heavily overloaded term. (For example, is /dev/tty a file? Is the
(major,minor) device number it might correspond to on a particular
filesystem at a particular moment a file? Is the integer that's returned
from open(/dev/tty, ...) a file? Is the tty device itself a file? I
think you've used file in all four senses.)
When I talk about a stream, I mean one end of a unidirectional pneumatic
tube. If it's the ingoing end, you stick some data in the tube and it's
carried away. If it's the outgoing end, you wait for some data to arrive
and then take it. Tubes all look the same. No pneumatic tube is a
storage device, but you may happen to know that it leads to a Frobozz
Magic Storage Device at the other end.
By the same token, stdin is never a file, but the data which appears
through stdin may ultimately be coming from a file, and it's sometimes
useful, in that case, to bypass stdin and access the file directly. The
way to handle this is to have a separate stdinFile :: Maybe File.
As for openFile: in the context of a certain filesystem at a certain
time, a certain pathname may refer to
* Nothing
* A directory
* A file (in the library sense); this might include things like
/dev/hda and /dev/kmem
* Both ends of a (named) pipe
* A data source and a data sink which are related in some qualitative
way (for example, keyboard and screen, or stdin and stdout)
* A data source only
* A data sink only
* ...
How to provide an interface to this zoo?
The dynamic-typing approach is to return some sort of Thing with a
complicated interface which is approximately the union of the interfaces
for each thing in the above list. Unsupported methods fail when called.
This is roughly what Posix does, except that directories are a special
case, and Nothing is very special (as perhaps it should be, but I'm not
sure).
The Haskell approach is, I guess, to use an algebraic datatype, e.g.
data FilesystemObject
= Directory Directory
| File File
| InputOutput PosixInputStream PosixOutputStream
| Input PosixInputStream
| Output PosixOutputStream
Here I'm using Posix*Stream for all streams backed by Posix
filehandles. I'm unsure whether NoSuchPath should be in there too.
You might say that this is annoyingly complicated. My first reaction is
tough--it's exactly as complicated as the reality it models. But there
should presumably be helper functions of types FilesystemObject-IStream
and FilesystemObject-OStream.
The other complication is that Posix makes you specify access rights
when you look up a path in the filesystem. This makes no sense, but it's
something we have to live with.
So I'd argue for replacing openFile with something like
data FilesystemObject = ...
openPath :: FilePath - IOMode - IO FilesystemObject
filesystemInputStream :: FilesystemObject - (IO?) IStream
data
Re: [Haskell-cafe] performance question
Stijn De Saeger wrote: data Bound = I Double | E Double deriving (Eq, Show, Ord) data Interval = Il Bound Bound | Nil Bound Bound deriving (Eq,Ord) isIn :: Double - Interval - Bool isIn r (Nil x y) = not (isIn r (Il x y)) isIn r (Il (I x) (I y)) = r = x r = y isIn r (Il (I x) (E y)) = r = x r y isIn r (Il (E x) (I y)) = r x r = y isIn r (Il (E x) (E y)) = r x r y If performance is the main concern, I would flatten the data structure: data Interval = IlII Double Double | IlIE Double Double | IlEI Double Double | IlEE Double Double | NilII Double Double | NilIE Double Double | NilEI Double Double | NilEE Double Double isIn :: Double - Interval - Bool isIn r (IlII x y) = r = x r = y isIn r (IlIE x y) = r = x r y isIn r (IlEI x y) = r x r = y isIn r (IlEE x y) = r x r y isIn r (NilII x y) = r x || r y isIn r (NilIE x y) = r x || r = y isIn r (NilEI x y) = r = x || r y isIn r (NilEE x y) = r = x || r = y Depending on your application you might not need all of those cases. Another neat trick you can pull is to take advantage of the fact that Double is actually a discrete type, like Int, and you can therefore get away with closed intervals only: data Interval = Il Double Double | Nil Double Double isIn :: Double - Interval - Bool isIn r (Il x y) = r = x r = y isIn r (Nil x y) = r x || r y But this requires nextLargestDouble and nextSmallestDouble functions. I don't know if Haskell provides them. Also, you could run into trouble with wider-than-Double intermediate values. Finally, if you never do anything with intervals except pass them to isIn, you can do this: type Interval = Double - Bool isIn r i = i r -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Top Level etc.
Jim Apple wrote: Does anyone have examples of these? This one scares the foo out of me: * It's not even safe in general to add a signature giving the same type that the compiler would infer anyway Here's an example: len :: [a] - Int len xs = let ?accum = 0 in len' xs len' [] = ?accum len' (x:xs) = let ?accum = ?accum + (1::Int) in len' xs *Main :t len' len' :: forall a. (?accum :: Int) = [a] - Int *Main len hello 0 len :: [a] - Int len xs = let ?accum = 0 in len' xs len' :: forall a. (?accum :: Int) = [a] - Int len' [] = ?accum len' (x:xs) = let ?accum = ?accum + (1::Int) in len' xs *Main :t len' len' :: forall a. (?accum :: Int) = [a] - Int *Main len hello 5 This happens as a side effect of the way that type inference currently works on recursive binding groups. It happens with typeclass dictionaries too, but it isn't observable because they can't be rebound in a local scope. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
Glynn Clements wrote: Keean Schupke wrote: Why is disk a special case? With slow streams, where there may be an indefinite delay before the data is available, you can use non-blocking I/O, asynchronous I/O, select(), poll() etc to determine if the data is available. [...] With files or block devices, the data is always deemed to be available, even if the data isn't in physical memory. I don't think this really captures the reason for the difference. It's not that select chooses not to do anything on the assumption that file access is fast. It's that it /can't/ do anything, because (drum roll) disk files are totally different from streams. The data you read from an input stream is being actively written by someone else. As the producer keeps writing, data will end up buffered in local memory until you read it. select() tells you when there's buffered data to read. If you're reading from a random-access file, there's no way it can tell you when the file data is buffered, because it doesn't know which part of the file you plan to read. The OS may try to guess for readahead purposes, but select()'s behavior can't depend on that guess. If streams were distinguished from random-access files at the OS level, the situation would be different. The fact that you create an input stream on top of a disk file indicates to the OS that you plan to read the file sequentially from that point. It's natural to use the same buffering model that's used for sockets, and select() can tell you when that buffer is non-empty. This is just like readahead, except predictable and under app control to some extent. Since you can create an arbitrary number of streams on a file, this mechanism provides all the functionality of NT's overlapped I/O model and quite a bit more. This is another example of why the world would be better off with the file/stream model. Have I convinced anyone? -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Existentials and type var escaping
Roberto Zunino wrote: foo, as defined above does not work (lazy patterns not allowed), and in foo y = E (case y of E x - x) a variable escapes. I also tried with CPS with no success. Is foo definable at all? I'm starting to think that it is not, and that there must be a very good reason for that... It's not definable, and there is a good reason. Existential boxes in principle contain an extra field storing their hidden type, and the type language is strongly normalizing. If you make the type argument explicit, you have foo (E t x) = E t x foo _|_ = E ??? _|_ The ??? can't be a divergent type term, because there aren't any; it must be a type, but no suitable type is available (foo has no type argument). You can't even use some default dummy type like (), even though _|_ does have that type, because you'd have to solve the halting problem to tell when it's safe to default. I'm less clear on how important it is that type terms don't diverge. I think it may be possible to write cast :: a - b if this restriction is removed, but I don't actually know how to do it. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
