Re: [Haskell-cafe] Re: capture of idioms and patterns
G'day all. Quoting Johannes Waldmann waldm...@imn.htwk-leipzig.de: you got this backwards: what some folks call idioms and (design) patterns actually *is* FP, because it is just this: higher order functions. And it's been there some decades (lambda calculus). That also explains the absence of any Design Patterns/Gang-of-Four kind of book for Haskell - it's just not needed. Err... no. The phrase design patterns is a shorthand for vocabulary of engineering experience. Zippers, continuation passing style, Church encoding... these are not what FP is, but they are specific techniques that engineers working in Haskell need to know to use the language effectively. You can think of design patterns as techniques that you need to overcome shortcomings in the language. That's why you need special techniques for, say, iterators in C++ or Java where in Haskell that comes more or less for free. But then, you need special techniques for mutable global state in Haskell, where in C++ or Java you get that for free. Or, to put it another way, nothing is ever free. There is no GoF-like book for Haskell because it's not an idea that needs promoting in printed form. We just point people to the wiki. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lambdacats
G'day all. Quoting Andrew Coppin andrewcop...@btinternet.com: Heh. unsafePerformDoggeh# still amuses me... I still have the original at full resolution of all the ones I did (including unsafeDoggeh#), plus a couple that didn't make it to the web site because they were deemed too obscure. For your viewing pleasure: http://andrew.bromage.org/pictures/eugenio.jpeg http://andrew.bromage.org/pictures/phillip.jpeg (And yes, I'm aware that there's one l in Philip Wadler. I think I was trying for a creative misspelling or something.) Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lambdacats
G'day all. Quoting Dan Doel dan.d...@gmail.com: Simon cat and Oleg cat are also missing, unfortunately. http://andrew.bromage.org/pictures/simon.jpeg http://andrew.bromage.org/pictures/oleg.jpeg I can't remember if this one made it to the site or not: http://andrew.bromage.org/pictures/dilimitd.jpeg Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tiger compiler in Haskell: annotating abstract syntax tree
G'day all. Quoting José Romildo Malaquias j.romi...@gmail.com: I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell. This might help: http://www.haskell.org/haskellwiki/Indirect_composite Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Transformers versus monadLib versus...
G'day all. Quoting Ertugrul Soeylemez e...@ertes.de: Do you realize at what level we are complaining? Yes, we're complaining at the level of the frustrated idealist, which is what many Haskell programmers are. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Transformers versus monadLib versus...
G'day all. Quoting Ertugrul Soeylemez e...@ertes.de: In its highest level not fragmenting the user base means going back to C++ and Windows. Ha. You wouldn't say that if you were familiar with the current state of C++ on Windows. Since nobody has come out and admitted it, here's the real problem: What constitutes the best API for a monad library is still a research problem. This is evidenced by the fact that a few times a year we get yet another paper which proposes a fundamental change to the API which would improve matters in yet another direction. Transformers, monadLib and MTL all have their respective strengths and weaknesses, but they are all considerably behind the state of the art, if you go by published research. Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Huffman Codes in Haskell
G'day all.
Quoting Andrew Coppin andrewcop...@btinternet.com:
What the...?
Oh, I see. It uses another package to handle the tricky sorting and
searching stuff. Well, yeah, that would make the code a bit shorter...
;-)
Even so, it's not nearly as elegant to behold as, say, the quicksort
algorithm, despite being of roughly similar complexity. Still, it's
shorter than what I had.
Ah, but the famous Haskell quicksort algorithm is optimised for brevity.
It's an executable specification of quicksort, not a practical sort
algorithm.
But honestly, it's just not that hard to do in linear time, assuming
the symbols are sorted by frequency:
data HuffmanTree a = Empty
| Node (HuffmanTree a) (HuffmanTree a)
| Leaf a
deriving Show
huffmanTree :: (Ord w, Num w) = [(w,a)] - HuffmanTree a
huffmanTree
= build . map (id Leaf) . sortBy (comparing fst)
where
build [] = Empty
build [(_,t)] = t
build ((w1,t1):(w2,t2):wts)
= build $ insertBy (comparing fst) (w1+w2, Node t1 t2) wts
Now if you want a real challenge, implement length-limited Huffman
codes. Here's a suggested interface:
-- There really should be a better traits typeclass for bit hackery,
-- but there isn't.
class (Integral w, Bits w) = WordType w where { wordBits :: w - Int }
instance WordType Word8 where { wordBits = 8 }
instance WordType Word16 where { wordBits = 16 }
instance WordType Word32 where { wordBits = 32 }
instance WordType Word64 where { wordBits = 64 }
minimalRedundancyCode :: (Ord w, Num w, WordType word) =
[(w,a)] - [(a,Int,word)]
-- minimalRedundancyCode returns an optimal prefix-free minimal-redundancy
-- code such that every code fits in a word of size w. An entry (a,b,w)
-- in the result means that the code for a is stored in the b least
-- significant bits of w.
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell and the Software design process
G'day all. Quoting aditya siram aditya.si...@gmail.com: I'm a little confused about this too. I've seen many functions defined like: f x = (\s - ...) which is a partial function because it returns a function and is the same as: f x s = ... Off the top of my head the State monad makes extensive use if this style. Is this bad? It's not inherently bad style. In the State/Reader monads, the passed-in parameter is part of the type: type State s a = s - (s,a) f :: Foo - State s a Since f has only one argument according to its type signature, it makes sense to give it only argument in its rules as well: f x = \s - ... This re-enforces the fact that s is an implementation detail of State. It is an error in Haskell to have multiple rules for a function with different arities. So this, for example, is illegal: f True = length f False [] = 3 f False (_:_) = 2 If there were a good reason for writing the first rule in a point-free manner, it would be perfectly reasonable to rewrite this using an explicit lambda. There are also performance issues which may be relevant. GHC doesn't break up lambdas to do let-floating, so if that's what you want, you may need to express it manually: data TreeSet a = Null | Singleton a | Doubleton a a | Branch a TreeSet TreeSet elem :: (Ord a) = TreeSet a - a - Bool elem Null = \p - False elem (Singleton p1) = \p - p == p1 elem (Doubleton p1 p2) = \p - p == p1 || p == p2 elem (Branch p' l r) = let elem_l = elem l elem_r = elem r in \p - if p p' then elem_l p else elem_r p Like all situations where you've got more than one way to express something, which one you pick depends on what you're trying to say. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Are there any gay haskelleres?
G'day all. Am 28.03.10 23:25, schrieb Ketil Malde: Look, Günther, I'll give you credit for trying, but you might as well accept the fact that using Haskell isn't going to get you laid. For what it's worth, I got away with naming a daughter Miranda. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lawless instances of Functor
G'day all. Quoting Derek Elkins derek.a.elk...@gmail.com: Ignoring bottoms the free theorem for fmap can be written: If h . p = q . g then fmap h . fmap p = fmap q . fmap g Setting p = id gives h . id = h = q . g fmap h . fmap id = fmap q . fmap g Using fmap id = id and h = q . g we get, fmap h . fmap id = fmap h . id = fmap h = fmap (q . g) = fmap q . fmap g Dan Piponi points out: When I play with http://haskell.as9x.info/ft.html I get examples that look more like: If fmap' has the same signature as the usual fmap for a type and h . p = q . g then fmap h . fmap' p = fmap' q . fmap g From which it follows that if fmap' id = id then fmap' is fmap. The free theorem for: fmap' :: forall a b. (a - b) - F a - F b assumes that F is already a Functor. That is, it shows that if there exists a valid fmap instance for F, then for any other function fmap' with the same signature as fmap, fmap' id = id implies fmap' = fmap. So if you want to invent a data type and fmap instance which satisfies law 1 but not law 2, then it needs to be a data type for which no valid fmap instance is possible *at all*. So it doesn't rule out the possibility completely, but it narrows down the search space considerably. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
G'day all. Quoting Dan Weston weston...@imageworks.com: Ouch. That's what happens when you let a machine do the translation. How about: Once your good name is trashed, you can live unabashed. Until you've lost your reputation, you never realize what a burden it was. -- Margaret Mitchell Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
G'day all. Quoting Richard O'Keefe o...@cs.otago.ac.nz: These lines of Haskell code find the Zumkeller numbers up to 5000 in 5 seconds on a 2.2GHz intel Mac. The equivalent in SML took 1.1 seconds. Note that this just finds whether a suitable partition exists; it does not report the partition. This takes 0.1 seconds on a 2GHz Dell running Linux: module Main where import Control.Monad import qualified Data.List as L primesUpTo :: Integer - [Integer] primesUpTo n | n 13 = takeWhile (= n) [2,3,5,11] | otherwise = takeWhile (= n) primes where primes = 2 : 3 : sieve 0 (tail primes) 5 sieve k (p:ps) x = let fs = take k (tail primes) in [x | x-[x,x+2..p*p-2], and [x `rem` p /= 0 | p-fs] ] ++ sieve (k+1) ps (p*p+2) pseudoPrimesUpTo :: Integer - [Integer] pseudoPrimesUpTo n | n = wheelModulus = takeWhile (= n) smallPrimes | otherwise = smallPrimes ++ pseudoPrimesUpTo' wheelModulus where largestSmallPrime = 11 verySmallPrimes = primesUpTo largestSmallPrime wheelModulus = product verySmallPrimes smallPrimes = primesUpTo wheelModulus wheel = mkWheel 1 [1] verySmallPrimes mkWheel _ rs [] = rs mkWheel n rs (p:ps) = mkWheel (p*n) (do k - [0..p-1] r - rs let r' = n*k + r guard (r' `mod` p /= 0) return r') ps pseudoPrimesUpTo' base | n = base + wheelModulus = takeWhile (= n) . map (+base) $ wheel | otherwise = map (+base) wheel ++ pseudoPrimesUpTo' (base + wheelModulus) -- Integer square root. isqrt :: Integer - Integer isqrt n | n 0 = error isqrt | otherwise = isqrt' ((n+1) `div` 2) where isqrt' s | s*s = n n (s+1)*(s+1) = s | otherwise = isqrt' ((s + (n `div` s)) `div` 2) -- Compute the prime factorisation of an integer. factor :: Integer - [Integer] factor n | n = 0 = error factor | n = primeCutoff = factor' n (primesUpTo primeCutoff) | otherwise= factor' n (pseudoPrimesUpTo (isqrt n)) where primeCutoff = 100 factor' 1 _ = [] factor' n [] = [n] factor' n (p:ps) | n `mod` p == 0 = p : factor' (n `div` p) (p:ps) | otherwise = factor' n ps -- The only function used from above is factor. zumkeller :: Integer - Bool zumkeller n | isPrime= False | isPrime= False | sigma `mod` 2 == 1 = False | sigma 2*n= False | otherwise = sigmaTest ((sigma - 2*n) `div` 2) (factors n) where isPrime = case factorn of [_] - True _ - False factorn = factor n sigma = product . map (sum . scanl (*) 1) . L.group $ factorn factors n = reverse [ f | f - [1..n `div` 2], n `mod` f == 0 ] sigmaTest 0 _ = True sigmaTest _ [] = False sigmaTest n (f:fs) | f n = sigmaTest n fs | otherwise = sigmaTest (n-f) fs || sigmaTest n fs main = print (filter zumkeller [1..5000]) Yes, I cheated by using a different algorithm. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What's the deal with Clean?
G'day all. Quoting wren ng thornton w...@freegeek.org: Sometimes in Haskell I've thought about how uniqueness typing would make something faster, but in general all the plumbing associated with it in Clean makes me feel like I'm writing systems-level code (i.e. C, asm) instead of using a high-level language. The extra plumbing really makes it feel dirtier to work with. That doesn't mean Clean is bad, but I think it does contribute to the cluttered feeling Haskellers get. I think you're right here. Haskell has developed something of an aversion to naming things that aren't important enough to have a name, such as variables whose only reason to exist is plumbing. We'd far rather spend effort on more higher-order functions, monads, combinators and points-freeness than name something that's unimportant. And the funny thing about this is that it usually works, because in Haskell, abstraction is cheap. I believe that this is the main reason why Haskell programmers haven't embraced arrows, despite their theoretical advantages: Every notation that has been implemented so far requires names for things that shouldn't need names. But as I said, it's a silly argument and folks should use whichever gives them warm fuzzies. I'd like to think that professional developers are a bit more scientific than this. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monoid wants a (++) equivalent
G'day all. Quoting John Meacham j...@repetae.net: (+) seems to imply to me that the operator is non-associative. Something like () or (+) would be better. I tend to agree. Moreover, and I realise this may be a losing battle, I want (++) to be the generic operator. I understand the argument. I even agreed with it at the time. In 1998, academic use of Haskell (both for research and education) was the most important imperative. Today, Haskell is officially cool, so the good names and operators should not be stolen by operations that are distinguished only by being less useful (e.g. by working on lists alone). Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monoid wants a (++) equivalent
G'day all. On Tue, Jun 30, 2009 at 08:02:48PM -0400, Daniel Peebles wrote: But we don't want to imply it's commutative either. Having something bidirectional like or + feels more commutative than associative to me. Quoting John Meacham j...@repetae.net: Not really, think of '++', which doesn't commute but is visually symmetric, or Data.Sequence., or the common use of to mean concatination in pretty printers. Other good examples are and ||. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: TernaryTrees-0.1.1.1 - An efficient ternary tree implementation of Sets and Maps
G'day all. Quoting Andrew Coppin andrewcop...@btinternet.com: That's just scary. I was just in the middle of writing the exact same thing! :-D (I read that very article...) When you're both done, please compare with the implementation that's been in Edison for about five years: http://www.cs.princeton.edu/~rdockins/edison/edison-core/src/Data/Edison/Assoc/ If you've got something that's an improvement (and believe me, it shouldn't be hard to improve on it), I'm sure that Rob would appreciate a patch. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type checking that I can't figure out ....
G'day Vasili.
This should do it:
remLookupFwd :: (ReVars m t) = SimplRe t - ReM m t (ReInfo t)
remLookupFwd re
= do fwd - gets resFwdMap
let { Just reinfo = fromJust (M.lookup re fwd) }
return reinfo
The FiniteMap lookup operation took its arguments in the opposite order.
That's really the only problem here AFAICT.
Wow, this brings back memories. I wrote this module about ten years ago,
and I'm shocked that it's still getting use. I'd appreciate a copy when
you're done updating it for the modern era.
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] the problem of design by negation
G'day all. Quoting Conal Elliott co...@conal.net: The main objection I have to the negative process (can't be done) is that is so often bogus. Proof by lack of imagination. I guess it works for Richard, though not for Michael's architect, because Richard is able to catch his bogus reasoning *and he is willing*** to do so, which requires humility and ego-strength. Conal is definitely on to something here. I've noticed that the best designers have this weird personality quirk that allows them to put all of their effort into pushing an idea, and then instantly back down and revise the moment that it's been shown that the idea won't work. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Looking for the fastest Haskell primes algorithm
G'day all. Quoting Dan Weston weston...@imageworks.com: Unless primesUpTo n goes from highest to lowest prime (ending in 2), I don't see how sharing is possible (in either space or time) between primesUpTo for different n. Given that it's a mistake for a library to leak memory, there are essentially three possibilities: Make the implementation impure, move responsibility onto the application, or only retain a finite number of primes between calls. This library: http://andrew.bromage.org/darcs/numbertheory/ only retains primes up to product [2,3,5,7,11,13,17], for several reasons: - It's convenient for the wheel algorithm to store all primes up to the product of the first k primes for some k. - It's ultra-convenient if the stored primes can fit in machine words. - For the types of numbers that we typically care about, it's useful to store at least all primes up to 2^(w/2) where w is the machine word size. - Storing more than a million seemed wrong. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Looking for the fastest Haskell primes algorithm
G'day all.
Quoting Eugene Kirpichov ekirpic...@gmail.com:
I'd suggest also
primesFrom :: Integer - [Integer]
This:
primes :: [Integer]
isn't as useful as you might think for a library, because it must, by
definition, leak an uncontrolled amount of memory. This:
primesUpTo :: Integer - [Integer]
is a better interface in that respect.
For the number theory library, I went overboard with a bunch of type
classes. I don't have the code handy, but this was the sort of thing:
class TestableProperty s a | s - a where
is :: s - a - Bool
data Prime = Prime
class TestableProperty Prime Integer where
is Prime n = {- ... -}
Then you could add instances for Fibonacci or whatever you wanted.
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] [OT] Plural forms of the word octopus [Was: Re: Marketing Haskell]
[Shifted to haskell-cafe.] G'day all. Quoting Benjamin L.Russell dekudekup...@yahoo.com: According to the Merriam-Webster Online Dictionary, it is topoi (see http://www.merriam-webster.com/dictionary/topos). Topoi form a certain class of category. You can study topous, you can prove theorems about topois and you can discover properties of topon. (That last one is an omega, so it's pronounced more like top-own.) Where did you find octoposi? In my ancient copy of Liddell and Scott. Here's the online entry: http://tinyurl.com/ck8gst Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Looking for practical examples of Zippers
G'day all. Quoting Gü?nther Schmidt gue.schm...@web.de: my quest for data structures continues. Lately I came across Zippers. Can anybody point be to some useful examples? This is a good example, currently in use in GHC: http://www.cs.tufts.edu/~nr/pubs/zipcfg-abstract.html Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unique monad?
G'day all. Quoting Lennart Augustsson lenn...@augustsson.net: I think Data.Unique is horrible and should be banned. It encourages a global variable style of programming that will just bite you in the end. In the sense that it doesn't give you anything that Monad.Supply or Control.Comonad.Supply doesn't, I agree. However, Data.Unique is a building block for the grubby implementation details of prettier, higher-level data structures (e.g. data structures that use hash consing). It's not supposed to be used at the application level. In that sense, it's no worse than unsafePerformIO. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] Haskell Weekly News: Issue 111 - March 28, 2009
G'day all. Quoting Krzysztof Skrzętnicki gte...@gmail.com: This paper from 1994: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.5611 begins point 1.1 with exactly that sentence. It doesn't seem to be quoted there, so one can assume this is the original source of that sentence. I'm not sure dough. I always it was a resynthesised version of this: Procedure calls are, from a theoretical point of view, glorified GOTO statements. -- Guy Steele, Lambda: The Ultimate GOTO Cheers, Andrew Bromage ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Design Patterns by Gamma or equivalent
G'day all. Quoting wren ng thornton w...@freegeek.org: Most of the (particular) problems OO design patterns solve are non-issues in Haskell because the language is more expressive. ...and vice versa. Some of the design patterns that we use in Haskell, for example, are to overcome the fact that Haskell doesn't have mutable global state. A number of other patterns can actually be written down once and for all (in higher-order functions like foldr, map,...) instead of needing repetition. This is also true in many OO languages. A lot of the GoF book, for example, can be implemented as libraries in Ada or C++. And then there are some things like monoids which fall somewhere between idiom and pearl. Things like monoids are constructions from algebra. Abstract algebra and design patterns have a lot in common. They're based on the same idea, in fact: When a pattern keeps showing up, define it and give it a name so you can talk about it independently of any specific implementation. Or to put it another way, category theory is the pattern language of mathematics. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] MonadTrans lift implementation
G'day all. Quoting Jonathan Cast jonathancc...@fastmail.fm: (By the way, you *do* have the equations lift (return x) = return x [...] Right. And you could, at least in principle, implement return this way in all monad transformers. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Improved documentation for Bool
G'day all.
On Mon, 2009-01-19 at 19:33 +, Andrew Coppin wrote:
My only problem with it is that it's called Bool, while every other
programming language on Earth calls it Boolean. (Or at least, the
languages that *have* a name for it...)
Jonathan Cast commented:
Except C++?
And perhaps more to the point, Boolean is an adjective, not a noun.
Therefore, it would be better reserved for a typeclass.
class (PartialOrder a) = JoinSemilattice a where
(||) :: a - a - a
class (MeetSemilattice a) = BoundedJoinSemilattice a where
bottom :: a
class (PartialOrder a) = MeetSemilattice a where
() :: a - a - a
class (MeetSemilattice a) = BoundedMeetSemilattice a where
top :: a
class (BoundedJoinSemilattice a, BoundedMeetSemilattice a) = Heyting a where
implies :: a - a - a
not :: a - a
not x = x `implies` bottom
class (Heyting a) = Boolean a where
{- the additional axiom that x || not x == top -}
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Improved documentation for Bool
G'day all. Quoting David Menendez d...@zednenem.com: Are there any instances of Boolean that aren't isomorphic to Bool? Sure. Two obvious examples: - The lattice of subsets of a universe set, where or is union and is intersection and not is complement with respect to the universe. - Many-valued logic systems. - Intuitionistic logic systems. - The truth values of an arbitrary topos (i.e. the points of the subobject classifier). Look up Heyting algebra for examples. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Improved documentation for Bool
G'day all. I wrote: - Intuitionistic logic systems. - The truth values of an arbitrary topos (i.e. the points of the subobject classifier). Sorry, I misread the question. These are _not_ instances of Boolean (or at least the latter isn't an instance in general). Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: Teach theory then Haskell as example
G'day all. Quoting Max Rabkin max.rab...@gmail.com: Good to have a recommendation -- my future CT lecturer has a hard time recommending anything not written by Mac Lane. One more suggestion: Conceptual Mathematics by Lawvere and Schanuel is the gentlest introduction that you're going to find. Cheers, Andrew Bromage ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Re: Comments from OCaml Hacker Brian Hurt
G'day all. Quoting Gracjan Polak gracjanpo...@gmail.com: I remember my early CS algebra courses. I met cool animals there: Group, Ring, Vector Space. Those beasts were very strong, but also very calm at the same time. Although I was a bit shy at first, after some work we became friends. I don't know about you, bu the word module threw me. That is probably the one name from algebra that clashes with computer science too much. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Comments from OCaml Hacker Brian Hurt
G'day all. Quoting John Goerzen jgoer...@complete.org: If I see Appendable I can guess what it might be. If I see monoid, I have no clue whatsoever, because I've never heard of a monoid before. Any sufficiently unfamiliar programming language looks like line noise. That's why every new language needs to use curly braces. If you're learning Haskell, which communicates the idea more clearly: * Appendable or * Monoid I can immediately figure out what the first one means. No you can't. It is in no way clear, for example, that Integers with addition are Appendable. I'm not saying that Monoid is the most pragmatically desirable term, merely that Appendable is misleading. And FWIW, I agree with everyone who has commented that the documentation is inadequate. It'd be nice if there was some way to contribute better documentation without needing checkin access to the libraries. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Comments from OCaml Hacker Brian Hurt
G'day all. Dan Weston wrote: Richard Feinman once said: if someone says he understands quantum mechanics, he doesn't understand quantum mechanics. But what did he know... Presumably not quantum mechanics. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Don't make 'show*' functions
G'day all. Quoting Jeff Heard jefferson.r.he...@gmail.com: I don't think that making Show a type class was a mistake. I don't either. Two main reasons: 1. [Char] should not be shown ['l','i','k','e',' ','t','h','i','s']. 2. Default implementations of Show can break abstractions by leaking implementation details. I think that we have long since overloaded the meaning of Show and made it ambiguous. There are multiple distinct reasons people use Show, and this gets confusing. It would be good if we as a community tried to nail down these different meanings that people tend to attach to Show and fork out new type classes that each encompass those meanings. Text is useful and often ignored as a means of debugging, inspecting, logging, and serializing. I tend to agree. Some thoughts: - Show is what print outputs and what GHCi reports. Therefore, to most programmers, it's primarily for human-readability regardless of what the standard says. - Read is barely useful as-is. Don't get me wrong; the read function has a very handy interface, especially if all you need is to convert a String into an Integer. But I'd wager that the majority of the most expert of expert Haskellers couldn't write a custom Read instance without constantly referring to the documentation and/or example code. In addition, very few people are aware of the performance characteristics of reads. - If you want serialisation and deserialisation, Show and Read are poorly-suited for it. A real solution requires handling tricky cases like versioning, redundancy (e.g. computed fields), smart constructors etc. - If what you actually want is parsing and/or pretty-printing, we have some great solutions for that. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Haskell re-branding exercise
G'day all. Quoting Sebastian Sylvan syl...@student.chalmers.se: Personally I find the current logo horrendous. I think it's ugly and intimidating at the same time. I don't really care too much which one of the proposals should win, just so long as I can weed out some of the ones I really hate. I guess this is one difference between the Haskell rebranding exercise and other corporate rebranding exercises: Nobody especially likes the current logo. (Disclaimer: It would be fair to say that there are some who don't hate it as much as Sebastian, but nobody really likes it.) Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: unique identifiers as a separate library
G'day all. Quoting Sebastian Fischer s...@informatik.uni-kiel.de: I have wrapped up (a tiny subset of) GHC's uniques into the package `uniqueid` and put it on Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/uniqueid First off, thanks for this. The main difference is due to my fear of depending on the foreign function `genSymZh` which I replaced by a global counting IORef. Why not depend on this instead? http://hackage.haskell.org/cgi-bin/hackage-scripts/package/value-supply Cheers, Andrew Bromage ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: [Haskell-cafe] Re: Functional version of this OO snippet
G'day all.
Thomas Davie wrote:
class IEngine a where
foo :: a - String
bar :: a - String - String
Apfelmus, Heinrich [EMAIL PROTECTED] replied:
You don't even need a type class, a simple data type is enough.
data Engine = Engine { foo :: IO (), bar :: String - IO () }
There is a tradeoff here, that you should be aware of.
1. Using typeclasses.
Pro: It works with the SPECIALIZE pragma.
Pro: You can put arbitrary data in the concrete data type which is
the instance of IEngine. (If you don't, incidentally, this is called
a traits typeclass.)
Con: You can't generate instances of IEngine dynamically at run-time
(at least without using unportable unsafeCast# magic). So you're
limited to only those implementations that you (possibly dynamically)
link in.
2. Using records.
Pro: Usually simpler, and using fewer lines of code.
Pro: You can generate new instances at will, and you're not limited
to that which you link in.
Con: Usually more explicit arguments passed around.
Con: If your methods involve polymorphism, then the record will turn
out to have a higher-rank type, which isn't valid Haskell 98.
This always works because all object methods expect a self argument.
That's not true for OO languages which have virtual constructors.
Haskell typeclasses support virtual constructors/factory methods just
fine, because the self type can appear anywhere in the signature,
including being the return value. The monad return method is one
example of this.
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Knight's Tour: solutions please
G'day all. Quoting Bertram Felgenhauer [EMAIL PROTECTED]: successors n b = sortWith (length . succs) . succs [...] successors n b = sortWith (length . (succs =) . succs) . succs [...] successors n b = sortWith (length . (succs =) . (succs =) . succs) . succs [...] These improved heuristics don't come cheap though. The heuristic is cheaper and more useful when the ply of the tree is low. It's more expensive and less useful when the ply is high. Moreover, deeper neighbour searches may only be useful in cases where the shallower searchers fail to settle on the best course of action. So something like the following might be better. Note that d here is an example only; I don't promise it's good. successors n b = sortWith heuristic . succs where heuristic p = let ps = succs p d = 5 - length ps `div` 2 in map length . take d . iterate (succs =) $ ps One more thing: Deeper neighbour searches are also unnecessarily expensive because they recompute succs a lot. It seems to me that if you memoed this, what you'd actually have is an explicit lazy search tree data structure. Hint hint. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Knight's Tour: solutions please
G'day all.
Quoting Don Stewart [EMAIL PROTECTED]:
So, team, anyone want to implement a Knight's Tour solver in a list
monad/list comprehension one liner? These little puzzles are made for
fast languages with backtracking monads
I conjecture that any one-liner won't be efficient.
Anyway, here's my ~30 min attempt. The showBoard and main are both very
quick and dirty, and I'm sure someone can do much better.
I particularly like the fact that changing Maybe to [] will make
knightsTour return all tours starting at the upper left-hand corner,
rather than just one. Warm fuzzy things rule.
Cheers,
Andrew Bromage
module Main where
import qualified Data.Set as S
import Data.List
import Data.Function
import Control.Arrow
import Control.Monad
import System
knightsTour :: Int - Maybe [(Int,Int)]
knightsTour size
= tour [(0,0)] (S.fromAscList [ (x,y) | x - [0..size-1], y -
[0..size-1],
x /= 0 || y /= 0 ])
where
jumps = [(2,1),(1,2),(2,-1),(-1,2),(-2,1),(1,-2),(-2,-1),(-1,-2)]
tour moves@(pos:_) blank
| S.null blank = return (reverse moves)
| otherwise = msum [ tour (npos:moves) (npos `S.delete` blank) |
npos - nextPositions pos ]
where
nextPositions = map snd . sortBy (compare `on` fst) .
map (length . neighbours id) .
neighbours
neighbours (x,y) = [ npos | (x',y') - jumps,
let { npos = (x+x',y+y') }, npos `S.member` blank ]
showBoard :: Int - [(Int,Int)] - ShowS
showBoard size
= inter bdr .
map (inter ('|':) . map (shows . fst)) .
groupBy ((==) `on` fst.snd) .
sortBy (compare `on` snd) .
zip [1..]
where
bdr = ('\n':) . inter ('+':) (replicate size (replicate width '-' ++))
. ('\n':)
width = length . show $ size*size
pad s = \r - replicate (width - length (s )) ' ' ++ s r
inter sep xs = sep . foldr (.) id [ pad x . sep | x - xs ]
main :: IO ()
main = do
a - getArgs
size - case a of
[] - return 8
(s:_) - return (read s)
putStrLn $ case knightsTour size of
Nothing - No solution found.
Just b - showBoard size b
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *not* to use Haskell for
G'day all. Quoting Lennart Augustsson [EMAIL PROTECTED]: People have been admitting to using Haskell like that for quite a while now. I think it's an excellent use of Haskell as a DSEL host. DSL is a proper superset of DSEL. Just saying. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *not* to use Haskell for
G'day all. Quoting Tom Hawkins [EMAIL PROTECTED]: Actually, Haskell is an excellent language for hard real-time applications. At Eaton we're using it for automotive powertrain control. Of course, the RTS is not running in the loop. Instead, we write in a DSL, which generates C code for our vehicle ECU. Bingo! And thanks for someone for admitting that they do this. :-) Hard real-time applications is a huge area, and not all of the code that you write is code that ends up running on the target. Generally, in DSL/MDD-style development, not very much of the code that you write ends up running on the target. In some cases, _none_ of the code you write ends up running on the target. Haskell is almost ideal for tasks like this. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Efficient parallel regular expressions
G'day all. Quoting Achim Schneider [EMAIL PROTECTED]: Considering that he's talking about a mud, I figure the grammar is a quite straightforward command = l[eft] | r[ight] | ... | t[ake] item | c[ast] spell That is, I'd be very surprised if you even need more than two or three characters lookahead, much less backtracking. In the case of a command followed by arguments, it would make more sense to use a keyword recogniser followed by a command-specific parser. One suggestion follows. Cheers, Andrew Bromage 8---CUT HERE---8 module KeywordMatch (keywordMatch) where import Data.List import Data.Function import Control.Arrow -- Exercise: Why would it be wrong to curry this function? keywordMatch :: (Ord k) = [([k],v)] - [k] - Maybe v keywordMatch kvs = compileTrie . generateTrie . sortBy (compare `on` fst) $ kvs data Trie k v = Trie (Maybe v) (Trie' k v) data Trie' k v = Node0 | Node1 k (Trie k v) | Node2 k (Trie k v) k (Trie k v) | Branch k (Trie' k v) (Trie k v) (Trie' k v) generateTrie :: (Ord k) = [([k],v)] - Trie k v generateTrie (([],v):rest) = Trie (Just v) (generateTrie' rest) generateTrie rest = Trie Nothing (generateTrie' rest) generateTrie' :: (Ord k) = [([k],v)] - Trie' k v generateTrie' [] = Node0 generateTrie' [(k:ks,v)] = Node1 k $ foldr (\k - Trie Nothing . Node1 k) (Trie (Just v) Node0) ks generateTrie' [(k1:ks1,v1),(k2:ks2,v2)] = Node2 k1 (generateTrie [(ks1,v1)]) k2 (generateTrie [(ks2,v2)]) generateTrie' kvs = gt . map (head.fst.head map (first tail)) . groupBy ((==) `on` head.fst) $ kvs where gt [] = Node0 gt [(k,kvs)] = Node1 k (generateTrie kvs) gt [(k1,kvs1),(k2,kvs2)] = Node2 k1 (generateTrie kvs1) k2 (generateTrie kvs2) gt kvs = let (l,(k,m):r) = splitAt (length kvs `div` 2) kvs in Branch k (gt l) (generateTrie m) (gt r) compileTrie :: (Ord k) = Trie k v - [k] - Maybe v compileTrie (Trie emptyCase trie') = let ctrie' = compileTrie' trie' in \key - case key of [] - emptyCase (k:ks) - ctrie' k ks compileTrie' :: (Ord k) = Trie' k v - k - [k] - Maybe v compileTrie' Node0 = \k ks - Nothing compileTrie' (Node1 k' t) = let t' = compileTrie t in \k ks - if k == k' then t' ks else Nothing compileTrie' (Node2 k1 t1 k2 t2) = let t1' = compileTrie t1 t2' = compileTrie t2 in \k ks - if k == k1 then t1' ks else if k == k2 then t2' ks else Nothing compileTrie' (Branch k' l m r) = let cl = compileTrie' l cm = compileTrie m cr = compileTrie' r in \k ks - case compare k k' of LT - cl k ks EQ - cm ks GT - cr k ks -- vim: ts=4:sts=4:expandtab ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Efficient parallel regular expressions
G'day all. Quoting Achim Schneider [EMAIL PROTECTED]: Considering that he's talking about a mud, I figure the grammar is a quite straightforward command = l[eft] | r[ight] | ... | t[ake] item | c[ast] spell That is, I'd be very surprised if you even need more than two or three characters lookahead, much less backtracking. In the case of a command followed by arguments, it would make more sense to use a keyword recogniser followed by a command-specific parser. One suggestion follows. Cheers, Andrew Bromage 8---CUT HERE---8 module KeywordMatch (keywordMatch) where import Data.List import Data.Function import Control.Arrow -- Exercise: Why would it be wrong to curry this function? keywordMatch :: (Ord k) = [([k],v)] - [k] - Maybe v keywordMatch kvs = compileTrie . generateTrie . sortBy (compare `on` fst) $ kvs data Trie k v = Trie (Maybe v) (Trie' k v) data Trie' k v = Node0 | Node1 k (Trie k v) | Node2 k (Trie k v) k (Trie k v) | Branch k (Trie' k v) (Trie k v) (Trie' k v) generateTrie :: (Ord k) = [([k],v)] - Trie k v generateTrie (([],v):rest) = Trie (Just v) (generateTrie' rest) generateTrie rest = Trie Nothing (generateTrie' rest) generateTrie' :: (Ord k) = [([k],v)] - Trie' k v generateTrie' [] = Node0 generateTrie' [(k:ks,v)] = Node1 k $ foldr (\k - Trie Nothing . Node1 k) (Trie (Just v) Node0) ks generateTrie' [(k1:ks1,v1),(k2:ks2,v2)] = Node2 k1 (generateTrie [(ks1,v1)]) k2 (generateTrie [(ks2,v2)]) generateTrie' kvs = gt . map (head.fst.head map (first tail)) . groupBy ((==) `on` head.fst) $ kvs where gt [] = Node0 gt [(k,kvs)] = Node1 k (generateTrie kvs) gt [(k1,kvs1),(k2,kvs2)] = Node2 k1 (generateTrie kvs1) k2 (generateTrie kvs2) gt kvs = let (l,(k,m):r) = splitAt (length kvs `div` 2) kvs in Branch k (gt l) (generateTrie m) (gt r) compileTrie :: (Ord k) = Trie k v - [k] - Maybe v compileTrie (Trie emptyCase trie') = let ctrie' = compileTrie' trie' in \key - case key of [] - emptyCase (k:ks) - ctrie' k ks compileTrie' :: (Ord k) = Trie' k v - k - [k] - Maybe v compileTrie' Node0 = \k ks - Nothing compileTrie' (Node1 k' t) = let t' = compileTrie t in \k ks - if k == k' then t' ks else Nothing compileTrie' (Node2 k1 t1 k2 t2) = let t1' = compileTrie t1 t2' = compileTrie t2 in \k ks - if k == k1 then t1' ks else if k == k2 then t2' ks else Nothing compileTrie' (Branch k' l m r) = let cl = compileTrie' l cm = compileTrie m cr = compileTrie' r in \k ks - case compare k k' of LT - cl k ks EQ - cm ks GT - cr k ks -- vim: ts=4:sts=4:expandtab ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Why 'round' does not just round numbers ?
G'day all. Quoting Mitchell, Neil [EMAIL PROTECTED]: With rounding to the nearest even integer for 0.5's you get 6, otherwise if you always round up you get 7. If you bias towards rounding up you get a general upwards trend as numbers are rounded, which is bad, while the even condition ensures that statistically it averages to the same thing. There are also many numeric algorithms for which the rounding pattern in the least-significant digit is somewhat systematic. A simple example might be this: x - round(x + 0.5) x - round(x - 0.5) x - round(x + 0.5) x - round(x - 0.5) ... etc If you try this procedure starting with, say, x = 1.5, you can see a clear difference between round-up and round-to-even. With round-up, the rounding error is keeps increasing as the procedure continues. With round-to-even, the error is bounded. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why 'round' does not just round numbers ?
G'day all. Quoting Daniel Fischer [EMAIL PROTECTED]: Who does such horrible things? Repeat after me: 1 is NOT a prime. Never, under no circumstances. The definition of prime is well-understood standard terminology, but that doesn't escape the fact that it's arbitrary and human-defined. I'll bet you insist on the non-triviality axiom for fields, too. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Why 'round' does not just round numbers ?
G'day all. Henning Thielemann suggested: In measured data the .5-case should be very rare - a null set? However I assume that .5 happens more often in practice - because of prior rounding, which was shown to be bad practice in this thread. The usual case in floating point is usually not 0.5, but some power of 0.5 just beyond the precision of the mantissa. And this is actually one of the most common cases in rounding, due to the fact that we use binary arithmetic. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: A heretic question
G'day aoll. Quoting Benjamin L.Russell [EMAIL PROTECTED]: Interesting argument. At first I thought that the following uncensored interview with Bjarne Stroustrup was a joke, but your argument makes it seem all the more plausible: That's not quite what I meant. What I meant is that Visual Basic script kiddie-ing may well be easy, real software development is hard. C++ is a hard tool to use well, but that's because it is doing a hard job. Some say that C++ was intentionally designed to be extremely difficult to use specifically in order for C++ programmers to earn those big bucks. Maybe this is just me, but if I had to choose a tool, I'd choose one that would be easy to use well. A paintbrush is easy to use, but hard to use well. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A heretic question
G'day all. On Sun, 2008-10-19 at 23:08 +0200, Achim Schneider wrote: I'm asking 'cos I'm learning C++ and can't get the proper motivation to do any program I can think of in it: If I need abstraction, I'm thinking Haskell or Scheme, and if I'm thinking performance, C itself more than suffices. Unless I'm working on a platform where memory is so tight that I can't afford the cost of vtables, EH, RTTI and extra stack usage, I always prefer C++ to C. Always. On the sorts of CPUs you find on desktops and servers, and even most embedded platforms these days, there is no advantage in using C over C++, and significant advantages in using C++ over C. The trouble is that C++ is a tool that's hard to use well. But that's why they pay us the big bucks, right? Quoting Derek Elkins [EMAIL PROTECTED]: I tend to use C++ whenever I strongly care about data representation (which is admittedly rarely.) Indeed. Having said that, type families mean that Haskell now gives you much finer control over data representation, though still not fine enough for many applications. The more general thing is that C++ gives you fine control over resources. Resources appear and disappear at predictable times, which in some applications is important. My last point is that C++ has a lot more tool support: compilers, libraries, frameworks, refactoring browsers and so on. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Name for Haskell based VPN Client/Server
G'day all. Quoting John Van Enk [EMAIL PROTECTED]: I'm working on a Haskell based VPN. I can't think of any good names, so I'm crowd sourcing it. The naming of code is a difficult matter, It isn't just one of your LAN party games; You may think at first I'm as mad as a hatter When I tell you, your code must have THREE DIFFERENT NAMES. First of all, there's the name that you use in publicity Such as Functional Forms, Nanocurses and HaRT, Such as Proof General Kit, vector-space, and hinotify, That will roll off the tongue and look good on slashdot. But I tell you, your code needs a name that's evoking, A name that inhabits the package namespace. Such as Text.PrettyPrint.HughesPJ, Data.ByteString, That's easily typed when importing MixedCase. But above and beyond, there's the name that's unique, And that is a name that is carefully picked. The one that's so mangled it may well be Greek; When it sits in slash-bin, it must never conflict. It's the name that will cause most dissent with your peers, Far, far more than the task it is meant to perform. It should work with your fingers, though not with your ears, So de-vowel-ified acronym soup is the norm. When you see a developer miffed and distracted, Tearing hair out in chunks or pacing without aim, They are greatly afflicted by anger protracted, Because somebody, somewhere, did not like the name. The simple, recognizable, Unrealizable, Deep, unattainable, singular Name. OK, having said that, I concur with those who have implicitly admitted that there are too many H's in the names of Haskell programs. I'd be tempted to pick a word starting with lan and put a v in front of it. My favourite VLANscape in particular. It sounds professional, and can be shortened to vlscape for the name of the executable. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Announcing OneTuple-0.1.0
G'day all. I asked: But more to the point: Can it send email? Quoting John Dorsey [EMAIL PROTECTED]: Can you give an example of a use case? I don't need one. It's not maximally flexible until it can send email. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Announcing OneTuple-0.1.0
G'day all. Quoting Lennart Augustsson [EMAIL PROTECTED]: But I called it One. That's a _terrible_ name. One, surely is (), just as Zero is Void. While I'm at it, I really don't like the lexical syntax of comments. Someone should fix that. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Model-driven development (was: Haskell participting in big science like CERN Hadrian...)
G'day all. Quoting Don Stewart [EMAIL PROTECTED]: How about EDSLs for producing high assurance controllers, and other robust devices they might need. I imagine the LHC has a good need for verified software components... On a related topic, I'm curious if anyone apart from me has been secretly using Haskell for model-driven-development-lite. My current boss, not being a programmer, doesn't care where the code comes from, so the following conversation is unlikely to happen. Still. other people must also have thought of doing this: Well, the reason why I've produced so much C++ lately is because I've been generating all the boilerplate automatically. What with? Glad you asked... Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Announcing OneTuple-0.1.0
G'day all. Quoting John Dorsey [EMAIL PROTECTED]: Contributions are welcome. The project could use a tutorial, and a decent test suite. Strict singleton tuples are planned for the next version. I hope it has a Monad instance. But more to the point: Can it send email? Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Shooting your self in the foot with Haskell
G'day all. On Wed, Oct 1, 2008 at 3:42 PM, Jake McArthur [EMAIL PROTECTED] wrote: Couldn't match expected type 'Deer' against inferred type 'Foot' No instance for (Target Foot) arising from use of `shoot' at SelfInflictedInjury.hs:1:0 Possible fix: add an instance declaration for (Target Foot) In the expression: shoot foot Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Health effects
G'day all. Quoting Adrian Neumann [EMAIL PROTECTED]: I often wonder how many cuts you need to divide a steak in n pieces. One, if the cut is allowed to be curved and self-intersecting. I think that the spirit of the problem, though is encapsulated in this question: Given a circle, what is the maximum number of pieces that you can divide it into by performing n straight cuts? This is a great problem to set undergraduates, because if you work out some small values of n on paper, you get: n #pieces 0 1 1 2 2 4 3 7 Most undergrads will stall at this point trying to work out how to place the third line to get 8 pieces, and probably come up with an incorrect justification for why it should be 2^n. The details are here: http://www.research.att.com/~njas/sequences/A000124 Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hmm, what license to use?
G'day all. Quoting Magnus Therning: Recently I received an email with a question regarding the licensing of a module I've written and uploaded to Hackage. I released it under LGPL. The sender wondered if I would consider re-licensing the code under BSD (or something similar) that would remove the need for users to provide linkable object files so that users can re-link programs against newer/modified versions of my library. Generally speaking, the Haskell community releases general-purpose libraries under a BSD-like licence. Programs are generally either released under the BSD-like licence or the GPL. The reason that we generally use the BSD-like licence for libraries is that libraries are intended to be maximally reusable. Hence, the de facto standard is a licence that allows for maximum reuse. There's nothing wrong with releasing a Haskell library under the LGPL. The biggest risk in doing so is that not everyone will use your library. The risk in picking yet another licence, one that satisfies your opinions on software freedom, is even more confusion. If the usual BSD-like licence doesn't do it for you, I would be concerned about adding yet another licence into the mix if you don't have to. Just use the LGPL, and add explicit exceptions if it makes you feel better. We know where we stand with GPL, LGPL and BSD. More licences causes more confusion. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there already an abstraction for this?
G'day. Quoting Jeremy Shaw [EMAIL PROTECTED]: I have an expression data-type: data Expr = Quotient Expr Expr | Product Expr Expr | Sum Expr Expr | Difference Expr Expr | Lit Double | Var Char deriving (Eq, Ord, Data, Typeable, Read, Show) And I want to write a function that will take an expression and automatically apply the identity laws to simplify the expression. [...] I would also be interested in alternative approaches besides the ones I outlined. A low-tech alternative that would work here is to use smart constructors. This approach avoids non-termination, and allows for quite general transformations. Example: sum :: Expr - Expr - Expr sum (Lit 0) y = y sum x (Lit 0) = x sum (Lit x) (Lit y) = lit (x+y) -- Call smart constructors recursively sum (Var v1) (Var v2) | v1 == v2 = product (Lit 2) (Var v1) -- Guards are OK sum x y@(Sum _ _) = foldl1 sum x . getTerms y $ [] -- So is complex stuff. -- This is a simple version, but it's also not too hard to write -- something which rewrites (x + 1) + (y + 2) to (x + y) + 3, say. -- Applying the Risch structure theorem is left as an exercise. where getTerms (Sum x y) = getTerms x . getTerms y getTerms e = (e:) sum x y = Sum x y -- And here's the default case lit :: Double - Expr lit = Lit -- Some constructors are trivial. Include them anyway. You can now either aggressively replace instances of data constructors with smart ones (except within the smart constructors themselves!) or write a single traversal which rewrites an expression: simplify :: Expr - Expr simplify (Sum x y) = sum (simplify x) (simplify y) simplify (Lit x) = lit x -- etc etc Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [m..n] question
G'day all. Quoting Richard A. O'Keefe [EMAIL PROTECTED]: I'm currently arguing that lists:seq(1, 0) should be [], not an exception. Oddly enough, I'm being beaten over the head with Haskell, of all things. [...] Does anyone remember why the definition of enumFromTo is the way it is? I don't know if this is the reason, but there's another nice property that enumerations have, namely: [p..q-1] ++ [q..r-1] == [p..r-1] -- if p = q = r If you think of the abstract semantics of ranges, this makes perfect sense. There needs to be a notation for empty ranges. Having said that, I don't know of a good reason why [5,5..5] is an infinte list of 5's. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [m..n] question
G'day. Quoting wren ng thornton [EMAIL PROTECTED]: I'm sure you know *why* it's an infinite list[1], but as for why that's useful I can't say. It has the feel of a bug in implementation, though it is ...consistent. Right. I have no problem with [5,5..5] being logically an anamorphism, but thinking abstractly about what I'd want it to mean, I'm pretty sure I don't want it to mean an infinite list of 5's. I asked a class of about a dozen bright undergrads about 10 years ago what they thought it should mean, and IIRC the consensus seemed to be split between [5] and [5,5]. Nobody correctly guessed what it actually did. So whether the behaviour is technically right or wrong, it violates the Principle of Least Surprise. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Propeganda
G'day all. Quoting Don Stewart [EMAIL PROTECTED]: We promise both safety and efficiency. We also provide (though don't promise) modularity, robustness and correctness, which is not something that Java gives you out of the box. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Reader monad, implicit parameters, or something else altogether?
G'day all.
Quoting Bjorn Buckwalter [EMAIL PROTECTED]:
I'd store the constants in a data structure along the lines of:
data AstroData a = AstroData
{ mu_Earth:: GravitationalParameter a
, leapSeconds :: LeapSecondTable
}
I would like to know if there is any consensus on what is the best way
to make such a data structure accessible in pure functions. Passing it
explicitly would be a mess.
In this situation, there isn't necessarily any shame in using a
top-level unsafePerformIO as long as it's well-hidden:
module AstroData (AstroData(..), globalAstroData) where
data AstroData = AstroData Int
-- You really don't want this function inlined. You also
-- really don't want this function to be polymorphic.
{-# NOINLINE globalAstroData #-}
globalAstroData :: AstroData
globalAstroData = unsafePerformIO $ do
d - return 42-- Or whatever
return (AstroData d)
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Reader monad, implicit parameters, or something else altogether?
G'day all. Quoting Richard A. O'Keefe [EMAIL PROTECTED]: Just an idiot-level question: so these constants are subject to revision, but *how often*? Good question. For leap seconds: - The data can change no quicker than once every 6 months. - The shortest time between changes was 6 months, and the longest (so far) was 7 years. - The mean change is once every 18 months. - You get just under 6 months' notice before a change comes into effect. (No more, no less.) For most programs, it's the last point that concerns me the most... What is the actual cost of recompiling and using them *as* constants, compared with the cost of rereading the stuff every time you run the program and passing it around? ...because the main cost probably isn't recompiling, it's redeployment. I don't know about this program in particular, but release cycles longer than six months are hardly uncommon in our business. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic Inclusions
G'day all. Quoting C.M.Brown [EMAIL PROTECTED]: But isn't this exactly the point I was trying to make!? The whole point, to me, in functional programming, is that we shouldn't have to worry about the underlying implementation. It is not exposing an underlying implementation detail to mandate that modules should have well-defined interfaces. If anything, it's enforcing good programming practice. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic Inclusions
G'day all. Quoting Thomas Davie [EMAIL PROTECTED]: To be honest, ghc compiles things so fast (at least on any of my systems) that I couldn't care less if it took 10 times as long (I would however like some added convenience for that time spent) Have you ever compiled GHC itself? Just curious what you'd think about a 10x speed hit there. If it helps, think about the lifetime of a program. If you assume that a program grows linearly over time, and that recompilations occur at a roughly constant rate, it follows that the time spent recompiling is O(n^2). Constant factors matter. If I compile a module on which lots of other modules depend, I have to do lots of recompilation... If I compile a module which is in a cyclic dependancy group, I have to do lots of recompilation, I don't see that there's a difference here. If you only change the implementation of a module, not its interface, you don't need to recompile anything that imports it. (At least, this is true at -O0, which if you care about fast recompilation because you're deep in development, you're probably doing.) That's a fair point about programming style, otoh, I don't think it's a reason to restrict users to not using cyclic dependancies. As previously noted, cyclic dependencies alone aren't the problem. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic Inclusions
G'day. Quoting C.M.Brown [EMAIL PROTECTED]: However I saw no real argument for not having cyclic inclusions. You say we shouldn't have to spend time writing hi-boot files, and yet you also think that GHC should not do it automatically. So we have to restrict all programmers to never writing cyclic inclusions? :) GHC generates .hi files for most modules automatically. The only reason why hi-boot files are needed for cyclic imports is because of the possibility that you can't generate a .hi file from the module alone. If you could do that, then you could support cyclic imports without needing hi-boot files. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic Inclusions
G'day all. Quoting Thomas Davie [EMAIL PROTECTED]: I'm not sure that it does make a lot of sense -- we allow (mutually) recursive functions, even though they come with an efficiency penalty. Why should we not allow (mutually) recursive modules, even though they too come with an efficiency penalty. The problem is not mutually recursive modules. Plenty of statically typed languages support mutually recursive modules. The problem is that it's impossible in general to say what the interface of a module is by examining the module alone. This is a very unusual property as real-world programming languages go. You could fix this by, for example, requiring that all symbols exported from a module have an explicit type annotation. Or, if you think that's not lazy enough, it could be an error to use an imported symbol that doesn't have an explicit type annotation. You could even formalise .hi-boot files if you were truly desperate. If the Haskell spec requires that multiple modules be analysed simultaneously (or multiple times to fixpoint), then that's a bug in the spec. Separate compilation is too important. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic Inclusions
G'day all. Quoting Thomas Davie [EMAIL PROTECTED]: Why is separate compilation important? I'm a little shocked that anyone on this list should have to ask this question. Two people have asked it now. The simplest answer is that unless your program fits in cache, it takes longer to compile two modules concurrently than it takes to compile them separately. This is even more true if one of those modules does not actually need recompilation. The longer answer is that in the Real World, programmer time is far, far more precious than computer time. Every second that the programmer waits for the computer to finish some task, there is a priority inversion. It's therefore highly desirable that jobs done by computer are as fast as possible or, failing that, as predictable as possible, so the programmer knows to do something else while waiting. Separate compilation puts a predictable upper bound on the amount of recompilation that has to be done given some set of changes. True, so does requiring recompilation of a package as a whole, but Haskell development would then be notorious for its sluggishness. I can understand your point about a module on it's own not being analyzable, and that that's an odd property -- on the other hand, the rapidly emerging atomic unit in Haskell is the package, so I see no reason why modules within one package shouldn't depend on each other. Implicit in my working definition of module is that a module has a well-defined interface. Am I the only one who has that understanding? (Well, me and David Parnas, at any rate.) For the record, I have no problem with modules depending on each other, so long as they only depend on their well-defined interfaces. Finally, as chris suggests, if separate compilation is important to you, why not have a flag in ghc -frequire-hi-boot or something? Well, if I wanted separate header files, and the inevitable multiple- maintenance headaches associated with them, I'd program in C. Except for mutually recursive modules, GHC can and does generate header files automatically, so I don't see why my time should be wasted doing the job of a compiler. If something is preventing the compiler from doing that job, then that something should be fixed. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic Inclusions
G'day all. Quoting Henning Thielemann [EMAIL PROTECTED]: As far as I know the real difficulties come from mutually recursive class definitions. I wouldn't be surprised, because that's a more blatant instance of the same problem. With classes and instances, there is no way to specify whether or not they are exported or not, which makes it that much harder to identify what the interface of a module is. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic Inclusions
G'day all. Quoting C.M.Brown [EMAIL PROTECTED]: Yes, I saw that, thanks! I guess this is because it's hard to compile a mutually recursive module... It's because you don't need to declare the types of exported definitions. Consider, this highly artificial example: module A where import B f (x,y) = g (x,'A') module B where import A g (x,y) = f (True,y) To infer the types of f and g, you need to analyse both modules together. And yes, some people think that this is a bug in the specification. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: on starting Haskell-Edu, a new education-related Haskell-related mailing list
G'day all. Quoting Abhay Parvate [EMAIL PROTECTED]: [EMAIL PROTECTED] [EMAIL PROTECTED] Cheers, Andrew Bromage ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] How would you hack it?
G'day. Quoting Andrew Coppin [EMAIL PROTECTED]: Right. So a Markov chain is actually a technical way of describing something that's intuitively pretty obvious? (E.g., PPM compression works by assuming that the input data is some sort of Markov chain with as-yet unknown transition probabilities.) Yes. In fact, DMC compression (which has been proven to be the same thing as PPM up to isomorphism) explicitly uses a Markov model. If you're curious, I recently put some code for building dynamic Markov models here. It's not pretty, but you might find it useful: http://andrew.bromage.org/darcs/dynamicmarkov/ Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mutually Recursive Modules
G'day all. Quoting Isaac Dupree [EMAIL PROTECTED]: Luckily, it is very often the case that your code will be better off anyway if refactored to have less module recursion. (though not always.) Nonetheless, I prefer not to leave the robustness of my code to luck. Besides, if I liked structuring code around artificial language restrictions, I'd be programming in C, not Haskell. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [ANN] bloomfilter 1.0 - Fast immutable and mutable Bloom filters
G'day all. Quoting Achim Schneider [EMAIL PROTECTED]: Please tell me that this isn't reversible. It isn't reversible. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] one-way monads
G'day all. Quoting Dan Piponi [EMAIL PROTECTED]: For any specific monad, m, it's usually possible to write a function m a - a. Actually, it's true less than 50% of the time. In particular, it's not true of any monad transformer. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List concat
G'day all. Quoting Andrew Coppin [EMAIL PROTECTED]: The function (++) :: [x] - [x] - [x] has O(n) complexity. That's not entirely true. When you call (++), it does O(1) work. If you evaluate k cons cells. it takes O(min(k,n)) work. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Unexpected lack of optimisation
G'day all. Quoting Simon Peyton-Jones [EMAIL PROTECTED]: Interesting thought. I think you're describing a possible extension to the SpecConstr transformation described in Call pattern specialisation for Haskell Without reading the paper, that sounds right to me. Here 'x' is free in 'g', but x's value is known at g's call sites. It's not enough just to know x is a cons inside g; we must also have access to z,zs. I would have thought that GHC already optimised this in a separate pass. Doesn't it do some kind of redundant case test elimination? And it's arguably a bad shortcoming that currently the mere act of lambda lifting can affect how effective SpecConstr is. Indeed. It also suggests to me that perhaps lambda lifting the pattern matching retries might _always_ be a good idea, given that the programmer has no way of controlling inlining for this kind of intermediately-generated function. Cheers, Andrew Bromage ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Unexpected lack of optimisation
G'day all. This is just a suggestion, but perhaps the problem isn't that retry isn't inlined, it's that it isn't specialised. IIRC, GHC does now specialise functions under what I assume would be these conditions: - There is a top-level case expression (possibly under some lets) which tests a function argument. - That function argument has a known constructor at a call site. The situation in Neil's code is almost identical, except that the top-level case expression is on a value passed by environment, not by function argument. Cheers, Andrew Bromage ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: [Haskell-cafe] A bright future for Haskell
G'day all. Quoting John Peterson [EMAIL PROTECTED]: Especially if SPJ decides to grow a beard. Unfortunately Paul is now clean shaven so maybe Haskell is in trouble. This explains why Clean never made it: Rinus Plasmeijer can't compete with Phil Wadler in the beard department. I should point out, for fairness, tht Mark Jones has suitable facial hair, and John Hughes and Ralf Hinze are not fair behind. John Peterson clearly should complete his beard, though. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Longest increasing subsequence
G'day all. Quoting Matt Amos [EMAIL PROTECTED]: http://en.wikipedia.org/wiki/Longest_increasing_subsequence The most efficient algorithm relies on destructive updates, so a simple translation doesn't seem possible. Given that it's based on binary search, you might like to try using a binary search tree. You may or may not have discovered that the quadratic algorithm has a more-or-less direct translation into Haskell using lazy arrays. Did you have a go at implementing that first? Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] instance Monad m = Functor m
G'day all. Quoting Jules Bean [EMAIL PROTECTED]: Other solutions, such as class Functor m = Monad m are frequently discussed. I see no H' ticket for it, though. Then add it. :-) You'll probably want to make it depend on Ticket #101, because making class hierarchies more granular generally depends on flexible instances. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Doing without IORef
G'day all. Quoting Jinwoo Lee [EMAIL PROTECTED]: Thanks everyone! Now I think using IORef is the most practical way to do this. Just a suggestion: Store it in a ReaderT instead of a StateT. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Dynamic typing makes you more productive?
G'day all. Quoting Jeremy Shaw [EMAIL PROTECTED]: I like to imagine it works like this: bad static type dynamic typing good static typing. More succinctly: Algol Smalltalk ML Or perhaps: C Ruby Haskell Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GADT rhymes with cat
G'day all. Quoting Ashley Yakeley [EMAIL PROTECTED]: GADT rhymes with cat. The d is silent, like the Danish godt, or the German Stadt, or the American trademark Bundt. I pronounce it so that it rhymes with ADT. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GADT rhymes with cat
G'day all. Quoting Jeremy Apthorp [EMAIL PROTECTED]: Clearly, this pronounciation is gay dee tea. I always new those types were a bit queer. Not that there's anything wrong with that. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system
G'day all. Quoting Andrew Coppin [EMAIL PROTECTED]: And yet they commonly pop up in Haskell. Can anybody put their finger on precisely why that is? One of the reasons why advanced type hackery shows up a lot in Haskell is that Haskell has never taken the easy way out. When confronted with an issue that doesn't seem to fit with purity, Haskell's answer has always been to apply more research, raid more category theory or generally think hard about the problem and come up with a clean solution, rather than sell out to impurity. And almost always, the theoretically clean solution has opened up new uses for types that were not previously considered. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A question about monad laws
G'day all. Quoting askyle [EMAIL PROTECTED]: Yup: bind f = f = id -- whence you can say (=) = flip bind Ah, yes. My point is that (as far as I can see) you cannot prove the properties of bind by only assuming identity and associativity for (=). One thing that may help is that if you can prove that fmap is sane: fmap (f . g) = fmap f . fmap g then the naturality of return is precisely its free theorem, and ditto for bind. So perhaps this law: (f = g) . h === f = (g . h) is actually the fmap law in disguise? Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A question about monad laws
G'day all. Quoting askyle [EMAIL PROTECTED]: So you're either not taking (=) as primitive or you're stating the additional property that there exists (=) such that f = g === (= g) . f (from which you can easily show that (f . g) = h === (f = h) . g ). If you wanted to prove that bind is natural, you would need to define bind, no? Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: (flawed?) benchmark : sort
G'day all. Quoting Adrian Hey [EMAIL PROTECTED]: I take it you mean something like .. Err... yes, I did. Where's the Eq instance for OrdWrap? Omitted for brevity. This may or may not satisfy the law: (compare a b) = EQ implies (a == b) = True. I think everbody agrees about that, but I can't tell from the code you've posted if it does in this case. The default implementation of compare says that. One thing that's not explicitly stated in the report is whether or not the instances of typeclasses like Eq or Ord need to do the same thing as[*] the default implementations. Does x /= y do the same thing as not (x == y)? What's disputed is whether or not this law should hold: (a == b) = True implies a = b Apart from possibly your good self, I don't think this is disputed. Quotient types, as noted elsewhere in this thread, are very useful. Their common use predates Miranda, so it's way too late to unbless them now. Well I hope you or anyone else hasn't used Data.Map or with OrdWrap keys because if so it's likely that the code has either been broken in the past, or is broken now (not sure which). For Data.Map, using an OrdWrap-like wrapper for keys is wrong, because it's not necessary. OrdWrap is for situations where you need to associate a value with a key which is, unsurprisingly, what Data.Map also does. As for sort, the behaviour hasn't been broken at any point in the past or present that I'm aware of, and a lot of people would strongly resist it if it ever were proposed that it be broken. Cheers, Andrew Bromage [*] Do the same thing as here means that they mean the same thing, but allows for the possibility that some implementation may be less stack-consuming, lazier or in some way more efficient than its default. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: (flawed?) benchmark : sort
G'day all. Quoting Conor McBride [EMAIL PROTECTED]: How depressing! Sorry, I don't understand that. Quotient types are good, but they're not the whole story. They just happen to be one use case with a solid history behind them. it's just that we need to manage information hiding properly, which is perhaps not such a tall order. It's my opinion (and I know I'm not alone in this) that modularity is probably the one thing that Haskell really hasn't (yet) gotten right. Haskell's implementation of modules/namespaces/whatever is the bare minimum needed to be minimally useful. It's a shame, because abstraction, in Haskell, is extremely cheap. It's often only one line, and you've got a compiler-checked abstraction that can't be accidentally confused with its representation. This should encourage micro-abstractions everywhere, but without submodules, namespaces or whatever you want to call them, these abstractions are easy to break (on purpose, not by accident). If only you could add a couple more lines of code, and instantly have your abstraction unbreakable. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: (flawed?) benchmark : sort
G'day all. Quoting Adrian Hey [EMAIL PROTECTED]: If that's supposed it imply you think I'm in a minority of one I don't think you've been following this thread very well. Sorry, that was a bit of hyperbole. Even the report uses the word equality in the prose. Indeed, and the only sensible meaning of equality that I can think of is _semantic_ equality. Two values are semantically equal if they mean the same thing. A concrete example of a quotient type that I had in mind is rationals. A rational is implemented as, for the sake of argument, a pair of integers. Two rational numbers, a/b and c/d, are equal iff ad = bc. That's what everyone means by equality for rationals. It's true that rationals have a normal form, and this can be enforced by a smart constructor and an unbreakable abstraction. But if you've got an unbreakable abstraction, then you've also got the mechanism to enforce observational equality. Moreover, not all quotient types have a one true normal form (e.g. regular expressions), and even in cases where there is a sensible normal form, it might be undesirable for reasons of performance or convenience. Besides there are good pragmatic safety and performance reasons why Haskell should provide at least one class that offers strong guarantees regarding equality and the (==) operator. Well, I haven't heard any reasons that have convinced me yet. No arguing over taste, of course. ..and has almost certainly been implicitly assumed by heaven knows what extant code (some of it in the standard libraries I suspect). Nobody has yet gone to the trouble of consulting either heaven or the source code (in whatever order is deemed appropriate) to see if this claim is true. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: (flawed?) benchmark : sort
G'day all. Adrian Hey wrote: This might be a reasonable thing to say about *sortBy*, but not sort as the ordering of equal elements should not be observable (for any correct instance of Ord). It should be impossible to implement a function which can discriminate between [a,a],[a,b],[b,a],[b,b] if compare a b = EQ. Nonsense. Consider a Schwartzian transform wrapper: data OrdWrap k v = OrdWrap k v instance (Ord k) = Ord (OrdWrap k v) where compare (OrdWrap k1 v1) (OrdWrap k2 v2) = OrdWrap k1 k2 It would be incorrect (and not sane) for sort [a,b] to return [a,a] in this case, though a case could be made that either [a,b] or [b,a] make sense. Quoting Jules Bean [EMAIL PROTECTED]: Stability is a nice property. I don't understand why you are arguing against this so aggressiviely. Stability is an occasionally very useful property. However, if there is a tradeoff between stability and performance, I'd prefer it if the library didn't choose for me. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A question about monad laws
G'day all. Quoting askyle [EMAIL PROTECTED]: If you use this presentation you also need the following law: (a . b) = c = (a = c) . b that is, compatibility with ordinary function composition. I like to call this naturality, since it's instrumental in proving return and bind to be natural transformations. Define: f = g = \x - f x = g fmap f xs = xs = return . f Then: fmap f . return = (expand fmap) \x - (return x = return . f) = (defn. of =) \x - (return = return . f) x = (left identity) \x - (return . f) x = return . f Therefore return is natural. Bind (or, equivalently, join) is left as an exercise. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: (flawed?) benchmark : sort
G'day all. Quoting David Menendez [EMAIL PROTECTED]: Adrian is arguing that compare a b == EQ should imply compare (f a) (f b) == EQ for all functions f (excluding odd stuff). Thus, the problem with your example would be in the Ord instance, not the sort function. Understood, and the Schwartzian transform might be better understood as sortBy rather than sort. As others have noted, this really is a question of what Eq and Ord mean. And the answer to that is: Whatever makes the most domain-specific sense. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: (flawed?) benchmark : sort
G'day all. Quoting Dan Weston [EMAIL PROTECTED]: 6.3.2 (The Ord Class): The Ord class is used for totally ordered datatypes. So... Double shouldn't be there, then? As previously noted, nowhere is it even required that x /= y should do the same thing as not (x == y). Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Functional programmer's intuition for adjunctions?
G'day all. Quoting Derek Elkins [EMAIL PROTECTED]: Of course, this is a concrete example using basic ideas of programming and not some intuitive analogy. I feel comfortable working with adjunctions, but I don't have some general analogy that I use. I think this is important. The concept of an adjunction isn't like that of a natural transformation. In Haskell, natural transformations are functions that respect the structure of functors. Since you can't avoid respecting the structure of functors (the language won't let you do otherwise), you get natural transformations for free. (Free as in theorems, not free as in beer.) Adjunctions, on the other hand, you have to make yourself. As such, they're more like monads. I use at least three distinct pictures when I'm working with monads: - Overloaded semicolon. - Functorial container (e.g. lists). - Term substitution system. ...but even that doesn't fully cover all the possibilities that monads give you. Monads are what they are, and you use them when it seems to make sense to implement the Monad interface for them. It's sometimes only obvious that an interface is conformed to after the event. For example, consider Data.Supply: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/value-supply-0.1 It's clear in retrospect that Supply is a comonad, but probably neither the paper authors nor the package author, smart as they are, noticed this at the time of writing, because you need experience with comonads to identify them. I think it's the same with adjunctions. Having said that, I think it makes sense to come up with some example pictures, much like the example pictures of monads that people use. Looking at those examples again: phi :: (F a - b) - (a - U b) phiInv :: (a - U b) - (F a - b) One thing that springs to mind is that an adjunction could connect monads and their associated comonads. Is that a good picture? Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
G'day all.
Quoting Cetin Sert [EMAIL PROTECTED]:
-- proposition
data Prp a = Var a
| Not (Prp a)
| Or (Prp a) (Prp a)
| And (Prp a) (Prp a)
| Imp (Prp a) (Prp a)
| Xor (Prp a) (Prp a)
| Eqv (Prp a) (Prp a)
| Cns Bool
deriving (Show, Eq)
This is probably the fastest:
vars :: Prp a - [a]
vars p = vars' p []
where
vars' (Var a) = (a:)
vars' (Not p) = vars' p
vars' (Or l r) = vars' l . vars' r
{- etc -}
vars' (Cns _) = id
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: The Proliferation of List-Like Types
G'day all. Quoting Neil Mitchell [EMAIL PROTECTED]: Yes, its the projection onto another type: [] = Nothing (x:xs) = Just (x, xs) Also known as msplit: http://www.haskell.org/haskellwiki/New_monads/MonadSplit Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
G'day all. Quoting Cetin Sert [EMAIL PROTECTED]: It is astonishing to see that your version actually performs the worst (at least on my machine). On your example, I'm not surprised: plong 0 = Var 0 plong n | even n= Or (Var n) (plong (n-1)) | otherwise = And (Var n) (plong (n-1)) This is effectively a singly linked list. I would expect my (well, I didn't invent it) to work better on something that didn't have this unique structure, such as: test 0 = Var 0 test n | even n= Or (Var n) (test (n-1)) | otherwise = And (test (n-1)) (Var n) Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: A question about monad laws
G'day all. Richard A. O'Keefe wrote: That's one of the warning signs I watch out for. Never compare floats for equality is a sure sign of someone who thinks they know about floats but don't. Quoting Roman Leshchinskiy [EMAIL PROTECTED]: Hmm. Personally, I've never seen an algorithm where comparing for exact equality was algorithmically necessary. One trick I've occasionally used is to avoid the need for a discriminated union of floating point and integer types by just using a floating point number. If you ignore bitwise operations and division/remainder, any integer operation that doesn't cause overflow on 32-bit integers will work just the same if you use IEEE-754 64-bit floating point numbers instead. That includes equality. Moreover, you even get a few more significant bits of precision. In these days of fast 64 and 128 bit words, it might not be entirely moral, but it works. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: A question about monad laws
G'day all. Quoting Thorkil Naur [EMAIL PROTECTED]: Finding the machine epsilon, perhaps, that is, the smallest (floating point, surely) number for which 1.0+machine_eps==1.0 would be a candidate? The machine epsilon is the smallest relative separation between two adjacent normalised floating point numbers. (The largest is the machine epsilon multiplied by the radix, more or less.) So as I understand it, if you're thinking relative error, this test: (fabs(x1-x2) machine_eps * fabs(x1)) should be true if and only if x1 == x2, assuming that x1 and x2 are nonzero and normalised. I've always had the impression that using the machine epsilon for pseudo-equality testing is fairly useless, especially if you can work out a meaningful problem-specific tolerance. What seems to be more useful is using the machine epsilon to compute an estimate of how much relative error your algorithm accumulates. I've seen this in a lot of Serious Numeric Code(tm), and I've done it myself (probably inexpertly) a few times. I haven't tried this, but I imagine that a computed relative error estimate could be useful for assisting your approximate-equality tests under some circumstances. Richard might know of some circumstances where this sort of thing would be useful. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
