Re: [Haskell-cafe] Readable GHC 7.6.3 docs (Bootstrapped)
Why does every section have a title=1.2.3 foo on the outer div? In Firefox this shows up as a useless tooltip when moving the mouse over the text. On 11/09/13 13:31, Obscaenvs wrote: At [1] you can find links to the GHC documentation that I use myself, since the official version is a bit too TimesNewRoman-y for my ...developed taste. It available in a downloadable Bzipped TAR aswell as being browsable online. [1] http://bugthunk.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Alternative name for return
On 13/08/13 17:38, Andreas Abel wrote: Indeed, I wished the 0-ary case would be more alike to the unary and binary case, cf. return f0 f1 $ a1 f2 $ a1 * a2 You could always write the above as pure f0 pure f1 * a1 pure f2 * a1 * a2 Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is the following implemented by a sparse matrix representation? type Graph n w = Array (n, n) (Maybe w)
The standard array types, such as Array (n,n) (Maybe w) will be implemented as a dense array. If you want to use a sparse matrix, you will explicitly have to ask for it. For instance by using something like IntMap (IntMap w) or Map (n,n) w or Array n (IntMap w). Each of these representations is slightly different, and there will be different trade-offs. Twan On 09/07/13 23:26, KC wrote: Is the following implemented by a sparse matrix representation? type Graph n w = Array (n,n) (Maybe w) -- -- Regards, KC ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RFC: rewrite-with-location proposal
On 25/02/13 07:06, Michael Snoyman wrote:
Quite a while back, Simon Hengel and I put together a proposal[1] for a new
feature in GHC. The basic idea is pretty simple: provide a new pragma that could
be used like so:
error :: String - a
errorLoc :: IO Location - String - a
{-# REWRITE_WITH_LOCATION error errorLoc #-}
Then all usages of `error` would be converted into calls to `errorLoc` by the
compiler, passing in the location information of where the call originated from.
Our three intended use cases are:
I think there is no need to have a separate REWRITE_WITH_LOCATION rule. What if
the compiler instead rewrites 'currentLocation' to the current location? Then
you'd just define the rule:
{-# REWRITE errorLoc error = errorLoc currentLocation #-}
I'm also pretty sure that something like this has been proposed in the past.
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RFC: rewrite-with-location proposal
On 25/02/13 13:41, Michael Snoyman wrote:
At that point, we've now made two changes to REWRITE rules:
1. They can takes a new ALWAYS parameters.
2. There's a new, special identifier currentLocation available.
What would be the advantage is of that approach versus introducing a single new
REWRITE_WITH_LOCATION pragma?
You are probably right. Ghc already has some logic in place for doing this with
'assert':
-- Return an expression for (assertError Foo.hs:27)
mkAssertErrorExpr = ..
finishHsVar name
= do { ignore_asserts - goptM Opt_IgnoreAsserts
; if ignore_asserts || not (name `hasKey` assertIdKey)
then return (HsVar name, unitFV name)
else do { e - mkAssertErrorExpr
; return (e, unitFV name) } }
So the check is name `hasKey` assertIdKey. I.e. it is a literal check whether
the name is assert. Maybe that could be extended to check whether the name is
declared as assert-like.
Of course the real solution is to have proper stack traces.
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining lambdabot
On 20/02/13 08:13, Jan Stolarek wrote: Dnia wtorek, 19 lutego 2013, Gwern Branwen napisał: On Tue, Feb 19, 2013 at 5:36 PM, Jan Stolarek jan.stola...@p.lodz.pl wrote: - remove unlambda, brainfuck and show from the repo. They are on hackage, no need to keep them here - these packages aren't even used in the build process. Where will they go? These packages are already on hackage: http://hackage.haskell.org/package/brainfuck http://hackage.haskell.org/package/show http://hackage.haskell.org/package/unlambda No need to keep them in the lambdabot repo. They are in the lambdabot *repository*, but in separate hackage packages. Are you suggesting that the source code of these packages is moved out to their own darcs repositories? Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Subject: ANNOUNCE: grid-3.0.1 (tile maps for board games or maths)
On 18/02/13 13:41, Amy de Buitléir wrote: I'm happy to announce a new major release of the grid package: http://hackage.haskell.org/package/grid https://github.com/mhwombat/grid/wiki (wiki) After taking a peek at the documentation: have you considered removing the size function from Grid? It is the only function that actually uses the type parameter 's'. If you really need it, I would suggest putting it in a separate class, class HasSize a s | a - s where size :: a - s It might also be useful to add a rectangular grid type where diagonally adjacent cells are also neighbors. Another interesting idea is to have modifier types that change which cells are neighbors, for example you could have class Colinear g x | g x where -- | Are three points separated by moves in the same direction? isColinear :: g - x - x - x - Bool -- neighbors are separated by diagonal moves newtype Diagonal g = Diagonal g instance (Grid g, Colinear g x) = Grid (Diagonal g) x where neighbors g x = [z | y - neigbhors x, z - neigbhors y , not (isColinear x y z)] newtype Rook g = ... newtype Knight g = ... -- etc. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ticking time bomb
On 31/01/13 09:16, Ketil Malde wrote: *MY* proposal is that: 0. Hackage sends an email to the previous uploader whenever a new version of a package is uploaded by somebody else. At least that way, I would be notified if it happened to my packages, and I would be able to check up on the situation, and rectify it. This is not to say that cryptographic signing is the wrong thing to do, but a very simple thing like this, which would probably take all of five minutes to implement, would reduce risk by a substantial amount. That is an excellent idea, and it should be very simple to add. Of course it doesn't stop all attacks, but it does stop the most obvious one. And it might also prevent some honest mistakes or errors in communication where someone uploads a forked package without permission. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sparse records/ADTs
On 24/10/12 12:08, Jon Fairbairn wrote:
Is there a convenient way of handling a data structure with lots
of fields of different types that may or may not be filled in?
Not sure about convenience, but here is a type safe solution with O(log n)
lookups and updates. The idea is to define a GADT tree type with a fixed layout:
-- define the structure
type MyT = TBranch (TLeaf A) (TBranch (TLeaf B) (TLeaf C))
-- a value level tree that uses that structure
type My = GTree MyT
You still have to define the paths to the members
pa = GL GH
pb = GR (GL GH)
pc = GR (GR GH)
But once you have that you can perform lookups and updates:
*Main glookup pc (gupdate pa (Just A) (gupdate pc (Just C) gempty))
Just C
It shouldn't be too hard to make a template haskell function that generates
these paths. Or perhaps the corresponding lenses.
Twan
{-# LANGUAGE DataKinds, KindSignatures, GADTs #-}
data TTree a = TEmpty | TLeaf a | TBranch (TTree a) (TTree a)
data GTree (t :: TTree *) :: * where
GEmpty :: GTree t
GLeaf :: a - GTree (TLeaf a)
GBranch :: GTree l - GTree r - GTree (TBranch l r)
data GPath (t :: TTree *) (a :: *) :: * where
GH :: GPath (TLeaf a) a
GL :: GPath l a - GPath (TBranch l r) a
GR :: GPath r a - GPath (TBranch l r) a
gempty :: GTree t
gempty = GEmpty
glookup :: GPath t a - GTree t - Maybe a
glookup GH (GLeaf x) = Just x
glookup (GL p) (GBranch x _) = glookup p x
glookup (GR p) (GBranch _ x) = glookup p x
glookup _ _ = Nothing
gupdate :: GPath t a - Maybe a - GTree t - GTree t
gupdate GH Nothing _ = GEmpty
gupdate GH (Just v) _ = GLeaf v
gupdate (GL p) v (GBranch l r) = GBranch (gupdate p v l) r
gupdate (GL p) v _ = GBranch (gupdate p v GEmpty) GEmpty
gupdate (GR p) v (GBranch l r) = GBranch l (gupdate p v r)
gupdate (GR p) v _ = GBranch GEmpty (gupdate p v GEmpty)
-- Example
data A = A deriving Show
data B = B deriving Show
data C = C deriving Show
type MyT = TBranch (TLeaf A) (TBranch (TLeaf B) (TLeaf C))
type My = GTree MyT
pa :: GPath MyT A
pa = GL GH
pb :: GPath MyT B
pb = GR (GL GH)
pc :: GPath MyT C
pc = GR (GR GH)
{-
*Main glookup pc (gupdate pa (Just A) (gupdate pc (Just C) gempty))
Just C
-}
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Platform Versioning Policy: upper bounds are not our friends
On 16/08/12 14:07, Chris Smith wrote: As a package author, when I release a new version, I know perfectly well what incompatible changes I have made to it... and those might include, for example: 1. New modules, exports or instances... low risk 2. Changes to less frequently used, advanced, or internal APIs... moderate risk 3. Completely revamped commonly used interfaces... high risk Would adding a single convenience function be low or high risk? You say it is low risk, but it still risks breaking a build if a user has defined a function with the same name. I think the only meaningful distinction you can make are: 1. No change to public API at all, user code is guaranteed to compile and work if it did so before. Perhaps new modules could also fall under this category, I'm not sure. 2. changes to exports, instances, modules, types, etc. But with the guarantee that if it compiles, it will be correct 3. changes to functionality, which require the user to reconsider all code. even if it compiles, it might be wrong For the very common case 2, the best solution is to just go ahead and try to compile it. A. Cabal files should get a new Compatibility field, indicating the level of compatibility from the previous release: low, medium, high, or something like that, with definitions for what each one means. You would need to indicate how large the change is compared to a certain previous version. Moderate change compared to 0.10, large change compared to 0.9. B. Version constraints should get a new syntax: bytestring ~ 0.10.* (allow later versions that indicate low or moderate risk) bytestring ~~ 0.10.* (allow later versions with low risk; we use the dark corners of this one) bytestring == 0.10.* (depend 100% on 0.10, and allow nothing else) Of course, this adds a good bit of complexity to the constraint solver... but not really. It's more like a pre-processing pass to replace fuzzy constraints with precise ones. Perhaps it would be cleaner if you specified what parts of the API you depend on, instead of an arbitrary distinction between 'internal' and 'external' parts. From cabal's point of view the best solution would be to have a separate package for the internals. Then the only remaining distinction is between 'breaking' and 'non-breaking' changes. The current policy is to rely on major version numbers. But this could instead be made explicit: A cabal package should declare what API version of itself it is mostly-compatible with. To avoid forcing the creation of packages just for versioning, perhaps dependencies could be specified on parts of a package? build-depends: bytestring.internal ~ 0.11 and the bytestring package would specify what parts have changed: compatibility: bytestring.internal = 0.11, bytestring.external = 0.10 But these names introduce another problem: they will not be fine-grained enough until it is too late. You only know how the API is partitioned when, in the future, a part of it changes while another part does not. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Improvement suggestions
On 15/08/12 17:01, José Lopes wrote: someFn docs = return concat `ap` (sequence $ intersperse (return \n) (map loop docs)) First of all, return x `ap` y = x `fmap` y or x $ y. fmap (or its infix synonym ($)) is the answer here, you could write: someFn docs = concat . intersperse \n $ mapM loop docs The function Data.List.intercalate is a compation of concat and intersperse, so you could write: someFn docs = intercalate \n $ mapM loop docs or, depending on your preference, someFn = fmap (intercalate \n) . mapM loop Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fixity declaration extension
On 14/08/12 13:46, Ketil Malde wrote: AntC anthony_clay...@clear.net.nz writes: I agree. I don't declare operators very often, and when I do I always struggle to remember which way round the precedence numbers go. [...] (Anything else we can bikeshed about while we're at it?) infixl * before + Perhaps before and after clearer than higher and lower? I would pick tighter than and looser than, but I suppose that before and after are also clear enough. Or maybe inside and outside? I don't think that we really need a new keyword for precedence declarations. The current infix would suffice if the default was for operators to be non-fix and of indeterminate precedence. Multiple fixity declarations for the same operator should then be allowed. Or perhaps just require that separate declarations use the same infix[lr]? keyword. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative functors with branch/choice ?
On 26/07/12 12:40, Евгений Пермяков wrote: class Applicative f = Actuative f where -- | select computation conditionally . Side effects of only one two alternative take place select :: f (Either a b) -- ^ selector - f (a - c) -- ^ first alternative - f (b - c) -- ^ second alternative - f c Can't you already define this function in terms of Applicative itself? I.e. select xs fs gs = sel $ xs * fs * gs where sel (Left a) f _ = f a sel (Right b) _ g = g b I assume that your intent is that `select` behaves differently from the one I defined here. But you need to specify in what way. Suppose it should work like if-then-else. Then you would perhaps have these laws: select (Left $ x) f g = f $ x select (fmap swapEither x) f g = select x g f I think this is a useful class to have, and I would support adding something like it to the standard library. Perhaps the arguments should be swapped to the same order as either, to give class Functor f = Selective f where eitherF :: f (a - c) - f (b - c) - f (Either a b) - f c The laws would then be: eitherF f g . fmap swapEither = eitherF g f eitherF f g . fmap Left = f eitherF f g . fmap Right = g -- follows from the other two laws every Monad is an instance via defaultEitherF ls rs xs = either ls rs = xs Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative functors with branch/choice ?
On 26/07/12 13:58, Евгений Пермяков wrote: As you can see, if I use select definition with Control.Applicative.*, I'll execute both l and r and the only choice will be, what result to drop. Both l and r, however, will be executed, and their side effects will take place. With select from my code only one action will be executed, depending on result of i, and only effects of one of actions (either l or r) will take place. I realize that, and that is why I insisted on laws to formalize this. Your instance for IO is a special case of a function that works for any Monad: defaultEitherF :: (Functor f, Monad f) = f (a - c) - f (b - c) - f (Either a b) - f c defaultEitherF ml mr mx = either (ml $$) (mr $$) = mx where ($$) :: Functor f = f (a - b) - a - f b f $$ x = ($ x) $ f (the version of this function in my previous post was not correct) I'm not sure, what categorical concept will correspond to this typeclass. Well, this type class kind of corresponds to the functionality of ArrowChoice. I believe that class corresponds to a (symmetric) monoidal structure on the dual category. Plus a whole bunch of junk you get from its super classes. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative functors with branch/choice ?
On 2012-07-25 22:22, Евгений Пермяков wrote: Let assume, that some computation takes argument and produces value Either a b. This computation may be represented in for different forms computePure :: a - Either b c computeMonad :: a - m (Either b c) computeApplicative :: app a - app (Either b c) computeArrow :: arr a (Either b c) = And now, having result, we need to execute several actions, making a choice, what actions to perform for Left and Right tags of Either. Pure function and monads are easy, as there is way to pattern-match on value and take actions depending on result. There is an extension to Arrow class that do the job -- ArrowChoice. However, I cannot find any way to make choice for Applicative. It seems that both Applicative and Alternative are not suited for it. So, it seems for me, that Applicative API should be extended with typeclass for making choice what actions to execute depending on result of some test (pattern matching). Is there any reasonable definition of such typeclass or clear explanation, why such typeclass is unneeded? The possible extension may look somehow like this: class Applicative a = Branching a where branch :: a (Either b c) - (a b - a d) - (a c - a d) - a d A nicer typeclass is perhaps the dual to applicative. Given a functor, (*) is equivalent to the function pair: class Functor f = Pairing f where pair :: (f a, f b) - f (a,b) -- pair (x,y) = (,) $ x * y -- (*) x y = ($) $ pair (x,y) You can form the dual of pair by flipping the arrows and replacing products by sums, which gives: class Functor f = Branching f where liftEither :: f (Either a b) - Either (f a, f b) Which looks almost equivalent to your Branching class. But I can't think of any non-trivial functors that are an instance of this class. Perhaps a better typeclass is the one where you keep the product on the result side: class Functor = Partitionable f where partitionEithers :: f (Either a b) - (f a, f b) You can build some useful functions on top of partionEithers, such as `partition` and `filter`. filter = fst . partition partition pred = partitionEithers . fmap side where side x = if pred x then Left x else Right x I don't know if it is enough for your ArrowChoice instance. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is (==) commutative?
On 2012-07-24 10:10, Christian Sternagel wrote: Dear all, with respect to formal verification of Haskell code I was wondering whether (==) of the Eq class is intended to be commutative (for many classes such requirements are informally stated in their description, since Eq does not have such a statement, I'm asking here). Or are there any known cases where commutativity of (==) is violated (due to strictness issues)? Strictness plays no role for Eq, since to test for equality both sides will have to be fully evaluated. I think (==) is supposed to be equivalence relation, which is symmetric (i.e. commutative); as well as reflexive and transitive. There are some cases of (==) not being reflexive, Floats being the most notable one, but many people consider that to be a bug. I can't think of any instances that violate symmetry. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is (==) commutative?
On 24/07/12 13:32, Frank Recker wrote: I agree, that (==) should be symmetric. However, it is easy to write Eq-instance, which violates this law: It is impossible to specify laws such as symmetry in Haskell, which is why they are usually stated in the documentation. However, this style of documentation is a relatively recent trend (last 5 years or so). I suspect that is why the documentation for the Eq class does not specify the laws for an equivalence relation. So in your formal verification, the symmetric property of every Eq-instance has to be an axiom. An alternative for equational reasoning is to not use Eq, but just directly use syntactic equality. I.e. write (=) instead of (==). I frankly don't know, whether the Haskell specification says anything about this. I checked, and it doesn't say anything about laws for Eq instances. The closest it comes is with the remark that The Ord class is used for totally ordered datatypes, but there is no requirement that Ord and Eq be coherent, or even that (==) and (/=) are coherent. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is (==) commutative?
On 24/07/12 14:39, Jonas Almström Duregård wrote: Hi, I suppose you need to define what commutativity means in the presence of undefined values. For instance if error 0 is different from error 1 then you do not have commutativity. Also nontermination needs to be considered, for instance (fix $ \x-x) == undefined typically fails to terminate but undefined == (fix $ \x-x) typically yields an error. Regards, Jonas In the usual Haskell semantics, all bottoms are considered to be the same. In other words, there is only one. You could implement this by setting undefined to nontermination, and error _ = undefined. In fact, the Haskell report does exactly this. Any error messages you get are only visible in IO land, where anything can happen anyway. So _|_ == x = _|_ holds for (almost) all types, except perhaps for (). Though in practice also undefined == () = undefined. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is (==) commutative?
On 24/07/12 14:44, timothyho...@seznam.cz wrote:
There's always this, for ALL types a :( So even where you would think that the
documentation can claim that a given Eq instance follows the law of
commutativity, it really cannot.
Once you invoke unsafePerformIO, you can break the type system, and probably
execute random assembly code and write to any memory location. So, at this point
all bets for the rest of the program are of. It is up to the programmer to
verify that all the necessary invariants still hold when you do unsafe stuff.
In other words, the issue here is not with a particular Eq instance, it is with
unsafePerformIO.
Essentially `unsafePerformIO (x :: IO Int)` is not really an Int, but rather a
value that behaves like one in most but not all cases.
Also, let a = unsafePerformIO x in (a,a) is *not* the same thing as
(unsafePerformIO x,unsafePerformIO x). For your entertainment:
λ do m - newEmptyMVar ;putMVar m 1 ; let {a =(unsafePerformIO (do v -
takeMVar m; putMVar m 2; return v)); b = (unsafePerformIO (do v - takeMVar m;
putMVar m 1 ; return v))} ; print (a == b); print (b == a)
False
False
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] arbitrary rank polymorphism and ghc language pragmas
On 05/07/12 17:18, rickmurphy wrote: Hi All: I've been working through some details in these papers [1], [2] and noticed a language pragma configuration that I hope you can confirm. When using explicit foralls in a data constructor, it appears that GHC 7.4.2 requires Rank2Types in the Language pragma for what the papers consider rank 1 types. Here's an example: data T = TC (forall a b. a - b - a) Am I correct, or is there another extension? The ExplicitForAll does not appear to support rank 1 types in data constructors. There is the PolymorphicComponents extension precisely for this use case. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fundeps and overlapping instances
On 24/05/12 14:14, AntC wrote: Simon Peyton-Jonessimonpjat microsoft.com writes: [from 7 Jul 2010. I've woken up this thread at Oleg's instigation http://www.haskell.org/pipermail/haskell-prime/2011-July/003491.html ] I'm not going to talk about Fundeps. This is about introducing overlapping instances into type families. But I mean dis-overlapped overlaps, with dis- equality guards on the instances: http://www.haskell.org/pipermail/haskell-prime/2012-May/003689.html This is essentially the same proposal as the July 2011 discussion, but a little updated with actual experience of type families in their more mature form. Example type family equations: type instance F Int = Bool type instance F a | a /~ Int = [a] -- explicit dis-equality guard Have you considered the alternative notation where multiple guards are allowed, as in normal function definitions? Something like: type instance F a | a ~ Int = Bool | Otherwise = [a] The last 'otherwise' clause is mandatory, matching should never fall through. Perhaps it could be an error if that were to happen, which would allow you to write closed type functions. Note that Otherwise could be declared in the library as type Otherwise = () :: Constraint I think this variant is almost equivalent to your proposal (so maybe it's just bikeshedding). It is also very similar to the IFEQ proposal, and you can desugar one in terms of the other. I also don't know how hard something like this would be to implement. The matching of type instances would be done in the same way as now, only their expanding is changed. The compiler will at this point have to look which guards are satisfied. In this example the first guard is a~Int, and this can not be checked until more is known about a. So, even though we have a known matching instance, it can not yet be expanded. Perhaps the notation instance F a | a /~ Int is better, because then a type family application can be expanded iff there is a matching instance. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Problem with forall type in type declaration
On 04/05/12 09:08, Magicloud Magiclouds wrote:
Hi,
Assuming this:
run :: Monad IO a - IO a
data Test = Test { f }
Here I'd like to set f to run, like Test run. Then what is the type of f?
The confusing (me) part is that, the argument pass to f is not fixed
on return type, like f1 :: Monad IO (), f2 :: Monad IO Int. So
data Test a = Test { f :: Monad IO a - IO a} does not work.
You need to explicitly add forall a. to the type of f. For example:
{-# LANGUAGE PolymorphicComponents #-}
run :: MonadIO m = m a - IO a
newtype Test = Test { f :: forall m a. MonadIO m a = m a - IO a }
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Reconstructing a tree from a list of its paths (to leaves)
On 10/04/12 09:55, Arnaud Bailly wrote: Hello, I am manipulating labeled multiway trees, some kind of lightweight XML notation. One thing I would like to be able to do is manipulating a tree as a list of (Path, Value). Generating such a list is easy but I am a little bit surprised to find it harder to reconstruct a tree, given such a list assuming some sensible properties (list is ordered, for example). I got the intuition this has already been tackled in one way or another in a functional setting in Haskell (I code in Java but using mostly functional constructs), but don't know where to look. The haskell solution would be to consider first how to turn a single (Path,Value) into a tree. Then you just combine these trees for all the paths by taking their union. I attached some code. Twan import qualified Data.Map as Map import Data.Map (Map) data Tree a b = Leaf b | Branch (Map a (Tree a b)) type Path a = [a] fromTree :: Tree a b - [(Path a,b)] fromTree (Leaf x) = [([],x)] fromTree (Branch xs) = [ (a:p,x) | (a,t) - Map.toList xs, (p,x) - fromTree t ] toTree :: Ord a = [(Path a,b)] - Tree a b toTree = foldr unionTree emptyTree . map (uncurry toTree1) toTree1 :: Ord a = Path a - b - Tree a b toTree1 [] b = Leaf b toTree1 (x:xs) b = Branch (Map.singleton x (toTree1 xs b)) emptyTree :: Tree a b emptyTree = Branch Map.empty unionTree :: Ord a = Tree a b - Tree a b - Tree a b unionTree (Branch xs) y | Map.null xs = y unionTree x (Branch ys) | Map.null ys = x unionTree (Branch xs) (Branch ys) = Branch (Map.unionWith unionTree xs ys) unionTree _ _ = error Can't have a leaf on the same level as something else ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: pipes-core 0.1.0
On 09/04/12 23:49, Paolo Capriotti wrote: I'm pleased to announce the release of version 0.1.0 of pipes-core, a library for efficient, safe and compositional IO, similar in scope to iteratee and conduits. http://hackage.haskell.org/package/pipes-core I have some issues with the function names used firstP :: Monad m = Pipe a b m r - Pipe (Either a c) (Either b c) m r secondP :: Monad m = Pipe a b m r - Pipe (Either c a) (Either c b) m r Why are firstP and secondP not called leftP and rightP? Those are the corresponding functions in Arrow. Similarly (***) should be called (+++). I also don't like `intersperse`, which does something completely different from its Data.List counterpart. intersperse :: Monad m = (a - Bool) - Pipe a (Maybe a) m r Data.List.intersperse :: a - [a] - [a] The documentation is also a bit misleading Yield Nothing when an input satisfying the predicate is received. To me this suggests that could behave like some kind of filter, intersperse p = pipe $ \x - if p x then Nothing else Just x A true intersperse analogue would be intersperse x = do y0 - await yield y0 forever $ do y - await yield x yield y The function you have defined is something like `yieldNothingBeforeMatching`. Do you have a use case for this function? Perhaps an interesting combinator would be -- | Run the first pipe until it yields a value, then run the second pipe until it yields, the the first pipe again, etc. alternate :: Pipe a b m r - Pipe a b m r - Pipe a b m r intersperse x = alternate idP (forever (yield x)) Although I have no idea if it is actually useful in practice. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mixing Unboxed Mutable Vectors and Parsers
On 2012-04-07 23:35, Myles C. Maxfield wrote: CC: Maintainers of STMonadTrans, Vector, and JuicyPixels Hello, I am writing a Haskell Attoparsec parser which will modify 2-d arrays of small values (Word8, Int8, etc.). My first idea was to simply parse all the deltas, and later apply them to the input list. However, I can't do that because the value of the deltas depend on the value they're modifying. My first pass at this program used a function of the form: p :: [[Word8]] - Parser [[Word8]] This approach works, however, the program uses far too much memory. Does the parser really need the input to determine what to do? Or is the parse tree the same regardless? In the latter case, you could perhaps rewrite it to p :: Parser ([[Word8]] - [[Word8]]) or when working with mutable vectors p :: MVector s Word8 - Parser (ST s ()) So instead of explicit deltas, the deltas can just be the function that applies them. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] is the evaluation order deterministic when using applicative with IO
On 16/03/12 10:45, Rouan van Dalen wrote:
Hi everyone.
I was wondering if I can make assumptions about the evaluation order of
the following code:
isTrue :: Int - IO Bool
isTrue val = pure (||) * boolTest1 val * boolTest2 val
{- boolTest1 is an inexpensive, quick check -}
boolTest1 :: Int - IO Bool
boolTest1 val = undefined
{- boolTest2 is a very expensive check -}
boolTest2 :: Int - IO Bool
boolTest2 val = undefined
When using Applicative in the isTruefunction, I would like to make use of
the short-circuit behaviour of || and rely on the fact that the boolTest1
will be executed first. The reason I am asking is because the boolTest
functions
are in the IO monad, instead of just returning pure Bool values.
The evaluation order is always from left to right with the instance
Applicative IO. However, both sides will still be evaluated. isTrue is
equivalent to:
isTrue val = do
t1 - boolTest1 val
t2 - boolTest2 val
return (t1 || t2)
If you want to avoid the side effects of boolTest2 when boolTest1
returns true, you will need to implement a monadic or, something like
orM ma mb = do
a - ma
if a then return True else mb
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: pipes-core 0.0.1
On 11/03/12 23:41, Chris Smith wrote: On Sun, Mar 11, 2012 at 2:33 PM, Twan van Laarhoventwa...@gmail.com wrote: I think you should instead move unwaits in and out of the composition on the left side: unawait x (p1+ p2) === (unawait x p1)+ p2 This makes idP a left-identity for (+), but not a right-identity, since you can't move unawaits in and out of p2. Not sure how we got to the point of debating which of the category laws pipes should break... messy business there. I'm going to be in favor of not breaking the laws at all. The problem here is that composition of chunked pipes requires agreement on the chunk type, which gives the type-level guarantees you need that all chunked pipes in a horizontal composition (by which I mean composition in the category... I think you were calling that vertical? no matter...) share the same chunk type. Paolo's pipes-extra does this by inventing a newtype for chunked pipes, in which the input type appears in the result as well. There are probably some details to quibble with, but I think the idea there is correct. I don't like this idea of implicitly just throwing away perfectly good data because the types are wrong. It shows up in the category-theoretic properties of the package as a result, but it also shows up in the fact that you're *throwing* *away* perfectly good data just because the type system doesn't give you a place to put it! What's become obvious from this is that a (ChunkedPipe a b m r) can NOT be modelled correctly as a (Pipe a b m r). Agreed. There are many things to be said for making sure that Pipe is a real category. I suppose the morally correct thing to do is, as you said, have a separate ChunkedPipe type. That would make the type system guarantee that there are no calls to 'unawait' in the second part of a categorical composition. The API could even look something like this: data Chunk data NoChunk data Pipe chunkiness a b m r await :: Pipe anyChunk a b m a yield :: b - Pipe anyChunk a b m () unawait :: a - Pipe Chunk a b m () runChunkedPipe :: Pipe Chunk a b m r - Pipe NoChunk a b m r -- composition in the category (+) :: Pipe NoChunk a b m r - Pipe NoChunk b c m r - Pipe NoChunk a c m r The following generalization of category composition is still fine: compose :: Pipe anyChunk a b m r - Pipe NoChunk b c m r - Pipe anyChunk a c m r But this would not be: almostEntirelyNotUnlikeCompose :: Pipe anyChunk a b m r - Pipe discardChunksHere b c m r - Pipe anyChunk a c m r By the way, a ChunkedPipe can be implemented not only as type ChunkedPipe a b m r = StateT [a] (Pipe a b m) r but also as type ChunkedPipe a b m r = CodensityT (Pipe a b m) r by using the 'feed' function to implement unawait. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: pipes-core 0.0.1
On 2012-03-11 14:09, Paolo Capriotti wrote: The Category law would be broken, though: unawait x id == yield x !== unawait x How did you get this equation? It's not even well-typed: unawait :: a - Pipe a b m () yield :: b - Pipe a b m () I would expect that (id unawait x) await !== unawait x await === return x because in the general case of (p unawait x) if is impossible to transform the unawaited value out of the composition. To do that you would need the inverse of p. You can get around this by having a special constructor for the identity. But then id !== arr id IMO, neither of these failed laws would be a big problem in practice, since no one will actually use identity pipes in combination with unawait. Or perhaps we should be satisfied when Pipe is a Semigroupoid? Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: pipes-core 0.0.1
On 2012-03-11 14:46, Paolo Capriotti wrote:
On Sun, Mar 11, 2012 at 1:25 PM, Twan van Laarhoventwa...@gmail.com wrote:
I would expect that
(id unawait x) await !== unawait x await === return x
There are several type errors in this equation, so I'm not exactly
sure what you mean. If you intended to write something like:
(id (unawait x return y)) await
!==
(unawait x return y) await
then I disagree, because both sides should evaluate to 'return y'. I'm
not sure why you would expect x to be returned, since there is no
'await' after 'unawait' in the middle pipe.
Oops, I got confused by () and (). The intended semantics of unawait is
unawait x await === return x
So what I was trying to write is
(id + unawait x) await
=== {by identity law}
unawait x await
=== {by behavior of unawait}
return x
But that this is impossible to implement, and instead what you get is
(id + unawait x) await === return () await === await
because in the general case of
(p unawait x)
if is impossible to transform the unawaited value out of the composition.
Why? The natual definition would be:
p + (unawait x p') == (yield x p) + p'
Right, but then take p==id, which gives
(id + (unawait x return ())) p'
===
((yield x id) + return ()) p'
===
return () p'
===
p'
So the unawait is not seen by p', whereas the identity law would give
(id + (unawait x return ())) p'
===
(unawait x return ()) p'
===
unawait x p'
I would like to get this latter semantics, and if the left side is id, it is
fine. However, in
(p :: Pipe a b r) + (unawait x q :: Pipe b c r) :: Pipe a c r
x has type b. You can not write this in a form like
unawait x' q :: Pipe a c r
because here x' would have type a. But if p == id, this is exactly what you
would like to get.
I'm extremely wary of this sort of reasoning, because failure of
invariants in simple situations are a symptom of something being
conceptually wrong in the abstraction.
Or perhaps we should be satisfied when Pipe is a Semigroupoid?
I don't think so, since we can always add formal identities. Usually,
though, failure of the identity law implies failure of associativity,
by just putting the failing identity in the middle of a composition.
A simple way to implement unawait that fails the identity law is by discarding
left-over unawaits inside a vertical composition. I.e.
unawait x + p === return () + p
q + unawait y === q + return ()
As long as you do this consistently for *all* vertical compositions, I don't see
how associativity is broken.
In the first case, with unawait on the left, you don't need to discard the
await. But I think it is probably more consistent if you do.
Anway, 'purePipe id' is now a failing identity, in the sense that composing with
it discards trailing awaits from the other thing composed with.
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: pipes-core 0.0.1
On 2012-03-11 17:30, Mario Blažević wrote: It's difficult to say without having the implementation of both unawait and all the combinators in one package. I'll assume the following equations hold: unawait x await = return x unawait x yield y = yield y unawait x (p1 unawait x) p2 = (p1 p2) * unawait x -- this one tripped me up first (unawait (x, y)) = unawait x I think you should instead move unwaits in and out of the composition on the left side: unawait x (p1 + p2) === (unawait x p1) + p2 This makes idP a left-identity for (+), but not a right-identity, since you can't move unawaits in and out of p2. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: pipes-core 0.0.1
On 2012-03-10 11:16, Paolo Capriotti wrote: Another issue is how to deal with unconsumed input. For that, there is a ChunkPipe type (in pipes-extra) with a specialized monad instance that threads unconsumed input along. You can see an example of ChunkPipe in action in this prototype http server by Jeremy Shaw: http://src.seereason.com/pipes-http-2/pipes-http-2/. Note that this is based on a old version of pipes-core, however. A nice way to deal with unconsumed input (from a user's perspective) would be a function -- | Pass some unconsumed input back upstream. -- The next @await@ will return this input without blocking. unawait :: Monad m = a - Pipe a b m () Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: pipes-core 0.0.1
On 2012-03-11 00:09, Mario Blažević wrote: On 12-03-10 05:19 PM, Twan van Laarhoven wrote: -- | Pass some unconsumed input back upstream. -- The next @await@ will return this input without blocking. unawait :: Monad m = a - Pipe a b m () The function may be called unawait, but there's nothing stopping you from inserting something into the stream that wasn't in the input to start with. I find that this approach breaks too many invariants. Which invariants does it break exactly? I.e. what properties do you expect to hold that fail when you can push arbitrary values back up-stream? Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding longest common prefixes in a list
On 2012-01-20 23:44, Gwern Branwen wrote:
On Fri, Jan 20, 2012 at 1:57 PM, Twan van Laarhoventwa...@gmail.com wrote:
Here is some example code (untested):
Well, you're right that it doesn't work. I tried to fix the crucial
function, 'atLeastThisManyDescendants', but it's missing something
because varying parts doesn't much affect the results when I try it
out on example input - it either returns everything or nothing, it
seems:
atLeastThisManyDescendants :: Int - Trie a - [CommonPrefix a]
atLeastThisManyDescendants minD trie@(Trie l d t')
| d minD = []
| null forChildren = [Prefix [] trie]
| otherwise = forChildren
where
forChildren = [ Prefix (x:pfx) nms
| (x,t) - Map.toList t'
, Prefix pfx nms - atLeastThisManyDescendants l t ]
It should be atLeastThisManyDescendants minD t, minD is a threshold for the
minimum numer of descendants, and it stays the same in the recursive call.
That's what you get for not testing your code :)
With the correct function I get a result like:
*Main mapM_ (print . prefix) $ atLeastThisManyDescendants 4 test1
gumi-
luka-
miku-a
miku-h
miku-m
miku-n
miku-p
miku-r
miku-s
miku-t
rin-
Notice that there are lots of miku-X prefixes found. This is probably not what
you want. What exactly do you want the algorithm to do? For example, is
obviously a prefix of every string, but it is not very long. On the other hand,
each string is a prefix of itself, but that prefix is shared by only one string
(usually).
By the way, the sort and compare adjacent pairs approach corresponds to
atLeastThisManyDescendants 2.
Twan
import qualified Data.Map as Map
-- A trie datatype
data Trie a = Trie { numLeafs, numDescendant :: !Int
, children :: Map.Map a (Trie a) }
instance (Show a) = Show (Trie a) where
showsPrec _ t = showString fromList . shows (toList t)
-- The empty trie
empty :: Trie a
empty = Trie 0 0 Map.empty
-- A trie that contains a single string
singleton :: Ord a = [a] - Trie a
singleton [] = Trie 1 1 Map.empty
singleton (x:xs) = Trie 0 1 (Map.singleton x (singleton xs))
-- Merge two tries
merge :: Ord a = Trie a - Trie a - Trie a
merge (Trie l d c) (Trie l' d' c')
= Trie (l+l') (d+d') (Map.unionWith merge c c')
fromList :: Ord a = [[a]] - Trie a
fromList = foldr merge empty . map singleton
toList :: Trie a - [[a]]
toList (Trie l _ c)
= replicate l []
++ [ x:xs | (x,t) - Map.toList c, xs - toList t ]
data CommonPrefix a = Prefix { prefix :: [a], names :: Trie a }
instance (Show a) = Show (CommonPrefix a) where
showsPrec _ (Prefix p ns) = shows p . showString ++ . shows (toList ns)
-- Find prefixes that have at least minD descendants.
-- when there is a prefix xs with =minD descendants, then shorter prefixes
will not be returned
atLeastThisManyDescendants :: Int - Trie a - [CommonPrefix a]
atLeastThisManyDescendants minD trie@(Trie l d c)
| d minD = [] -- too few descendants
| null forChildren = [Prefix [] trie] -- all longer prefixes have too few
descendants, but this prefix doesn't
| otherwise = forChildren -- there are longer prefixes with enough
descendants, return them
where
forChildren = [ Prefix (x:pfx) names
| (x,t) - Map.toList c
, Prefix pfx names - atLeastThisManyDescendants minD t ]
test1 = fromList
[chorus-kiminoshiranaimonogatari.ogg
,chorus-mrmusic.ogg
,choucho-lastnightgoodnight.ogg
,dylanislame-aikotoba.ogg
,electriclove-ã¨ã¬ã¯ããªãã¯ã»ã©ã-korskremix.ogg
,gumi-bacon8-justhangingaround.ogg
,gumi-iapologizetoyou.ogg
,gumi-montblanc.ogg
,gumi-mozaikrole.ogg
,gumi-ãããã¼ã·ã³ã»ãµã¤ã¶.ogg
,gumi-showasengirl.ogg
,gumi-sweetfloatflatsã¹ã¤ã¼ãããã¼ãã¢ãã¼ã.ogg
,gumi-timewarpedafterchoppingmystagbeetle.ogg
,gumi-ãªãªã¸ãã«æ²-ä»ããã·ã¡ã°ãª.ogg
,gumi-ãã¯ãªãªã¸ãã«è¦ªå.ogg
,kaito-byakkoyano.ogg
,kaito-flowertail.ogg
,kasaneteto-tam-ochamekinouéé³ããå¹ã£åãããã¡ããæ©è½.ogg
,len-crime-timetosaygoodbye.ogg
,len-fireâflower.ogg
,len-ponponpon.ogg
,lily-prototype.ogg
,luka-apolxcore-waitingforyou.ogg
,luka-dimããã¤.ogg
,luka-dion-myheartwillgoon.ogg
,luka-dirgefilozofio-dirgeasleepinjesus.ogg
,luka-ã¢ã´ã¢ãã-doubelariatããã«ã©ãªã¢ãã.ogg
,luka-emon-heartbeats.ogg
,luka-emonloid3-ããã¼ããã¼.ogg
,luka-everybreathyoutake.ogg
,luka-ãªãªã¸ãã«-garden.ogg
,luka-justbefriends.ogg
,lukameiko-gemini.ogg
,luka-milkyway.ogg
,luka-ãã¿ãã-ããã.ogg
,luka-tic-tick.ogg
,luka-torinouta.ogg
,luka-zeijakukei-shounenshoujo.ogg
,luka-åæã«ã¢ãã¡-nologic-ä½ã£ã¦ã¿ã.ogg
,luka-é§ç®äººé.ogg
,meiko-artemis-awake.ogg
,miku-9ronicleãã©ãã.ogg
,miku-acolorlinkingworld-ãã®ä¸çã®ä¸ã§.ogg
,miku-acolorlinkingworld-éãè±.ogg
Re: [Haskell-cafe] Right tree structure for complicated problem
On 2012-01-22 00:39, Pierre Penninckx wrote: So here is what I want to achieve: I'd like a program that calculates the time needed for water to flow out of a circuit made out of tube. The rules are : - There are multiple sources of water and only one exit. - The water can only take one path from a source to the exit. - Of course, a source of water contains a certain amount of water at the beginning. Is this a maximum flow problem? If so, I would suggest using a standard algorithm to solve it. See wikipedia [1] for an explanation. The fgl library has a haskell implementation of such an algorithm [2]. Twan [1] http://en.wikipedia.org/wiki/Maximum_flow_problem [2] http://hackage.haskell.org/packages/archive/fgl/5.4.2.4/doc/html/Data-Graph-Inductive-Query-MaxFlow.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] instance (Enum a) = IArray UArray a
On 20/01/12 16:31, Mikhail Arefiev wrote: Is there a reason why there is no instance of (Enum a) = IArray UArray a (other than that it will require OverlappingInstances and/or IncoherentInstances if e. g. UArray of Bools is used in the same code)? ... Does having such thing make any sense? The problem is that there are Enum instances for things for which to/fromEnum doesn't make sense, such as Double, Float and Integer. Prelude fromEnum (12345678901234567890 :: Integer) -6101065172474983726 You wouldn't want your Integers to be stored as Ints in an array. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding longest common prefixes in a list
On 20/01/12 18:45, Gwern Branwen wrote:
Recently I wanted to sort through a large folder of varied files and
figure out what is a 'natural' folder to split out, where natural
means something like4 files with the same prefix.
My idea for an algorithm would be: build a trie for the input strings,
and then look for the deepest subtries with more than one child.
For example, a trie containing the strings
chorus-kiminoshiranaimonogatari.ogg
chorus-mrmusic.ogg
choucho-lastnightgoodnight.ogg
looks like:
root (3 items)
c (3 items)
h (3 items)
o (3 items)
r (2 items)
u (2 items)
s (2 items)
- (2 items)
k (1 item)
i (1 item)
minoshiranaimonogatari.ogg
m (1 item)
r (1 item)
music.ogg
u (1 item)
c (1 item)
ho-lastnightgoodnight.ogg
Where actually the lines with more than one character are also subtrees
of subtrees of subtrees.
Here is some example code (untested):
import qualified Data.Map as Map
-- A trie datatype
data Trie a = Trie { numLeafs, numDescendant :: !Int
, children :: Map.Map a (Trie a) }
-- The empty trie
empty :: Trie a
empty = Trie 0 0 Map.empty
-- A trie that contains a single string
singleton :: Ord a = [a] - Trie a
singleton [] = Trie 1 1 Map.empty
singleton (x:xs) = Trie 0 1 (Map.singleton x (singleton xs)
-- Merge two tries
merge :: Ord a = Trie a - Trie a - Trie a
merge (Trie l d c) (Trie l' d' c')
= Trie (l+l') (d+d') (Map.unionWith merge c c')
fromList :: Ord a = [[a]] - Trie a
fromList = foldr merge empty . map singleton
toList :: Ord a = Trie a - [[a]]
toList (Trie l _ c)
= replicate l []
++ [ x:xs | (x,t) - Map.toList c, xs - toList t ]
data CommonPrefix a = Prefix { prefix :: [a], names :: Trie a }
atLeastThisManyDescendants :: Int - Trie a - [CommonPrefix a]
atLeastThisManyDescendants minD trie@(Trie l d t)
| d minD = []
| null forChildren = [Prefix [] trie]
| otherwise = forChildren
where
forChildren = [ Prefix (x:pfx) names
| (x,t) - Map.toList c
, Prefix pfx names - atLeastThisManyDescendants n t ]
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Current Haskell report URL
On 23/11/11 23:02, Tom Murphy wrote: Is there a reason that the Haskell 2010 report is in a subdirectory of haskell.org/onlinereport http://haskell.org/onlinereport (which currently points to the Haskell98 standard)? http://www.haskell.org/onlinereport/ -- Haskell98 http://www.haskell.org/onlinereport/haskell2010/ -- Haskell2010 If it's for historical reasons - because books etc. use this URL for the 98 standard, then I'd highly recommend making a new directory called currentreport or something (if there isn't one already). IMO, a book author should expect that an URL like http://www.haskell.org/onlinereport/ could change to point to a new version, since it doesn't mention a version number or date anywhere. The most sensible directory structure would be: http://www.haskell.org/onlinereport/ http://www.haskell.org/onlinereport/haskell98 http://www.haskell.org/onlinereport/haskell2010 Where the onlinereport/index.html says something like: Latest version: * haskell2010 Previous versions: * haskell98 Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict
On 18/11/11 06:44, Johan Tibell wrote: On Thu, Nov 17, 2011 at 9:21 PM, Johan Tibelljohan.tib...@gmail.com wrote: I'm not entirely happy with this formulation. I'm looking for something that's clear (i.e. precise and concise, without leaving out important information), assuming that the reader already knows how lazy evaluation works at a high level. Ideas? This reads a bit better to me: I actually much prefer the original formulation. In particular, you should keep examples together with the rules they illustrate. * key and value function arguments passed to functions are evaluated to WHNF before the function body is evaluated, and function arguments passed to functions sounds a bit redundant. Either say arguments passed to functions or function arguments. Also before the function body is evaluated says something about evaluation order, does that really matter for strictness? * All key and value arguments passed to functions are evaluated to WHNF before the function body is evaluated * keys and values returned by high-order function arguments are evaluated to WHNF before they are inserted into the map. Keys and values not returned by higher order functions, but passed in directly are also evaluated to WHNF (per the first rule), so that qualification is unnecessary. Just say: * keys and values are evaluated to WHNF before they are inserted into the map. I also think 'stored' is better here than 'inserted', because the latter might give the impression that it only applies to the insert function, and not to things like map. insertWith (+) k undefined m == undefined etc. As Roman suggested, use = here instead of ==. To really illustrate the first rule, insertWith (+) is not enough, you would really need a function that doesn't use the value, so insertWith (\new old - old) k undefined m = undefined But that is just nitpicking. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Superset of Haddock and Markdown
On 18/11/11 09:18, Ivan Lazar Miljenovic wrote: On 18 November 2011 19:06, Roman Cheplyakar...@ro-che.info wrote: Maybe have a switch that enables markdown and disables markup-related features of haddock (everything except linking to identifiers/modules, I believe), so that we don't affect existing docs. Then make it possible to pass this flag through cabal. As in have an opt-in Cabal field? For a cabal field, we could just have haddock be the default markup language. Something like: DocMarkupLanguage: Haddock | Markdown | Plain | Html | ... -- default is Haddock But before worrying about that, such a possibility should exist in haddock. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to speedup generically parsing sum types?
On 03/11/11 11:16, Bas van Dijk wrote:
...
instance (Constructor c, GFromJSON a, ConsFromJSON a) = GFromSum (C1 c a) where
gParseSum (key, value)
| key == pack (conName (undefined :: t c a p)) =
gParseJSON value
| otherwise = notFound $ unpack key
{-# INLINE gParseSum #-}
notFound :: String - Parser a
notFound key = fail $ The key \ ++ key ++ \ was not found
{-# INLINE notFound #-}
Perhaps relying on Attoparsec backtracking for picking out the right
alternative from the sum is the problem. You could try it with Maybe:
class GFromSum f where
gParseSum :: Pair - Maybe (Parser (f a))
instance (Constructor c, GFromJSON a, ConsFromJSON a)
= GFromSum (C1 c a) where
gParseSum (key, value)
| key == pack (conName (undefined :: t c a p))
= Just (gParseJSON value)
| otherwise = Nothing
instance (GFromSum a, GFromSum b) = GFromSum (a :+: b) where
gParseSum keyVal = (fmap L1 $ gParseSum keyVal)
| (fmap R1 $ gParseSum keyVal)
{-# INLINE gParseSum #-}
instance (GFromSum a, GFromSum b) = GFromJSON (a :+: b) where
gParseJSON (Object (M.toList - [keyVal]))
| Just p - gParseSum keyVal - p
gParseJSON v = typeMismatch sum (:+:) v
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Attoparsec: Limiting Parsers to N Bytes, or Combing Parsers?
On 24/09/11 05:21, Evan Laforge wrote: hex2 = (+)$ ((*16)$ higit)* higit higit = subtract (fromEnum '0')$ satisfy isHexDigit color = Color$ hex2* hex2* hex2 How is subtract (fromEnum '0') supposed to convert a hex digit to an Int or Word8? I think you need digitToInt (or an equivalent function) for that. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc 7.0.3 view patterns and exhaustiveness
On 2011-09-21 22:06, Brent Yorgey wrote: On Tue, Sep 20, 2011 at 10:31:58PM -0400, Richard Cobbe wrote: numVarRefs :: Term - Integer numVarRefs (view - Var _) = 1 numVarRefs (view - App rator rand) = numVarRefs rator + numVarRefs rand numVarRefs (view - Lam _ body) = numVarRefs body -- numVarRefs (view - _) = error bogus This is a known limitation. Your particular example is perhaps not so hard to figure out, but what if we had view :: Bool - Bool view x = search for a counterexample to the Goldbach conjecture; if one is found, return x, otherwise return False foo (view - False) = ... But in Richard's example, all possible values of the result of view are handled. For your foo example, the equivalent would be. foo (view - False) = ... foo (view - True) = ... Ghc should be able to detect this case, and not issue a warning. All that needs to be done is check if the function can be rewritten to numVarRefs t = case view t of ... Where ... is exhaustive. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fwd: Re: Period of a sequence
On 2011-06-27 13:51, Steffen Schuldenzucker wrote: Could you specify what exactly the function is supposed to do? I am pretty sure that a function like seqPeriod :: (Eq a) = [a] - Maybe Integer -- Nothing iff non-periodic cannot be written. What about sequences that can be specified in terms of 'iterate': import Control.Arrow (first) -- Return the non-repeating part of a sequence followed by the repeating part. -- -- iterate f x0 == in a ++ cycle b -- where (a,b) = findCycle f x0 -- -- see http://en.wikipedia.org/wiki/Cycle_detection findCycle :: Eq a = (a - a) - a - ([a],[a]) findCycle f x0 = go1 (f x0) (f (f x0)) where go1 x y | x == y= go2 x0 x | otherwise = go1 (f x) (f (f y)) go2 x y | x == y= ([], x : go3 x (f x)) | otherwise = first (x:) (go2 (f x) (f y)) go3 x y | x == y= [] | otherwise = y : go3 x (f y) -- diverges if not periodic seqPeriod :: Eq a = (a - a) - a - Integer seqPeriod f x0 = length . snd $ findCycle f x0 Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Links into list
On 02/05/11 13:10, John Sneer wrote: Simply: I would like to have direct access into several places in a very long list. Maybe you could use a zipper. Or just maintain the list split into chunks. So l' = [stuffBefore,hi,stuffAfter]. Or if you want to be able to use each element of hi as a kind of pointer, then l'=[stuffBefore] ++ map (:[]) hi ++ [stuffAfter] Now modification becomes just a matter of replacing the appropriate chunk. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Testing Implementation vs Model - Records or Type Classes?
On 08/04/11 11:54, Heinrich Apfelmus wrote:
Hello,
I'm writing a small Haskell library for functional reactive programming.
The core of the library consists of two data types and several
primitives. However, I have programmed this core *twice*: once as a
*model* that displays the intended semantics, and once as the actual
*implementation* to be used in production code.
...
Haskell Café, what are your suggestions and ideas?
...
For reference, here the full signature of the core combinators:
data Event a
data Behavior a
instance Functor Behavior
instance Applicative Behavior
instance Functor Event
instance Monoid (Event a)
filter :: (a - Bool) - Event a - Event a
apply :: Behavior (a - b) - Event a - Event b
accumB :: a - Event (a - a) - Behavior a
You don't need MPTCs to generalize the filter function:
-- this class is useful beyond this FRP library,
-- you might already be able to find it on hackage somewhere
class Functor f = Filterable f where
filter :: (a - Bool) - f a - f a
-- filter p . fmap f == fmap f . filter (p . f)
-- filter (const True) == id
-- filter p . filter q == filter (\x - p x q x)
The apply and accumB functions are harder. Is the Behavior
implementation for the model really different from the one of the
implementation, which seems to be {initial::a, changes::Event a}? If
not, you could just generalize that type by making the event type a
parameter
data GenBehavior e a = GB a (E a)
If this is not the case, then instead of MPTCs you could also try type
families,
class ... = FRP event where
data Behavior event
apply :: Behavior event (a - b) - event a - event b
accumB :: a - event (a - a) - Behavior event a
I don't know whether this is any better than the MPTC approach, though.
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The mother of all functors/monads/categories
Max Bolingbroke wrote:
I don't actually know what the right name for this data type is, I
just invented it and it seems to work:
-- () :: forall a b. t a b - (forall c. t b c - t a c)
newtype Wotsit t a b = Wotsit { runWotsit :: forall c. t b c - t a c }
There is of course no reason to prefer () to (), so you can instead
quantify over the first argument as opposed to second one:
newtype Wotsit' t a b = Wotsit' { runWotsit' :: forall c. t c a - t c b }
liftWotsit' :: Category t = t a b - Wotsit' t a b
liftWotsit' t = Wotsit' (() t)
lowerWotsit' :: Category t = Wotsit' t a b - t a b
lowerWotsit' t = runWotsit' t id
instance Category (Wotsit' t) where
id = Wotsit' id
t1 . t2 = Wotsit' (runWotsit' t1 . runWotsit' t2)
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there good place to post Haskell alorithms/data structures that follow Steven Skiena's book on algorithm design and also Haskell code snippets that follow some of Knuth's books?
Casey Hawthorne wrote: Is there good place to post Haskell alorithms/data structures that follow Steven Skiena's book on algorithm design and also Haskell code snippets that follow some of Knuth's books? These code snippets don't seem to fit with Hackage. You could make some pages for them on the Haskell wiki. If it is structured as a tutorial (which your suggestion of hatorial suggests), then you should add it to http://haskell.org/haskellwiki/Category:Tutorials Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The 8 Most Important GSoC Projects
Ivan Lazar Miljenovic wrote: I've been thinking of doing something similar for a year or so now, but there's one big problem that I can think of: how to deal with functions that don't have an explicit type signature in the source. My understanding is that to derive these signatures at checking time would require using something like the GHC API, which immediately reduces the niceness and portability of such a tool/library. As a simple approximation, you could consider functions without type signatures to have changed if their implementation or any function they depend on has changed. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell.org re-design
Christopher Done wrote: That's true, it's a nice idea but in practice it's hard to know where to focus. I've gone with a left nav. I've built up the HTML which is cross-browser (ie6/7/8/opera/firefox/safari/chrome compat), still need to add some bits but I can tomorrow import it into a wikimedia skin. It's kind of easy to re-shuffle now that I've built it. http://82.33.137.16/haskell-website/ Feedback would be appreciated. One has to think, what do I really want to see on the home page? Two important things I am missing are: * A link to the documentation. Perhaps as a button in the top row. * A link to tutorial(s) / Real World Haskell. Besides the download button, these are the important things that new users look for when they land on the home page. This design looks too much like the Haskell Community homepage, not the Haskell Programming Language home page. Some more things: * I think that the links on the left are confusing and unnecessary, since there is already a menu at the top. * Why would there be a 'links' page? All links fall either under 'community' or 'news' or 'download'. * Perhaps have a tab named 'events', and put all the event stuff there? * (minor) the buttons on the top row have a dent at the top (in Firefox 3.6 on windows) Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Asynchronous exception wormholes kill modularity
Bas van Dijk wrote: ... However now comes the problem I would like to talk about. What if I want to use modifyMVar_ as part of a bigger atomic transaction. As in: block $ do ... modifyMVar_ m f ... From a quick glanse at this code it looks like asynchronous exceptions can't be thrown to this transaction because we block them. However the unblock in modifyMVar_ opens an asynchronous exception wormhole right into our blocked computation. This destroys modularity. Would it work if 'block' adds a layer of blocking and 'unblock' removes one layer of blocking? So block a = do modifyIORef blockLevel (+1) result - a modifyIORef blockLevel (-1) return result unblock a = do modifyIORef blockLevel (-1) result - a modifyIORef blockLevel (+1) return result canThrowExceptions = (= 0) `liftM` readIORef blockLevel Although it is probably a better idea to not use block/unblock at all in user code. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Map unionWith generalization
Hans Aberg wrote: For example, in Map String Integer (sparse representation of monomials) compute the minimum value of all associative pairs with the same key (the gcd); if only one key is present, the absent should be treated as having value 0. So unionWith min xs ys will not work, because unionWith will always apply the identity to the remaining value when one key is missing, whereas it should be sent to 0. If missing keys represent 0, then wouldn't this work? intersectionWith min xs ys Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Capped lists and |append|
John Millikin wrote: Earlier today I uploaded the capped-list package; I didn't think there would be any interest, since it's a relatively trivial data structure, but already there's been three emails and an IRC convo about it. Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Any ideas? This seems like a useful structure, since several people have described it, but some of the semantics seem troublesome. Some ideas: append :: Monoid c = CappedList c a - CappedList c a - CappedList c a append (Cap a) (Cap b) = Cap (a `mappend` b) This also leads to an instance Monoid (CappedList c): instance Monoid c = Monoid (CappedList c) where mempty = Cap mempty mappend = append You could also make the combining function flexible: appendWith :: (c - d - e) - CappedList c a - CappedList d a - CappedList e a The problem with this definition is that it doesn't really respect the structure of the second list: the entire list has to be traversed just to update the cap. More random ideas: -- this is bind in the CappedList _ a monad bindCap :: CappedList c a - (c - CappedList d a) - CappedList d a bindCapF :: Functor f = CappedList c a - (c - f (CappedList d a)) - f (CappedList d a) Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
John Van Enk wrote: Hi Heinrich, I think I like Ring more than Necklace or Tom's suggestion of Circular. I chose Ring simply because that's what I was searching for when I wanted the data structure. The package will be named data-ring, so that should hopefully be enough to clue in the user that it's not dealing with the mathematical concept. The mathematical concept would likely also go in Data, unfortunately. See for example Data.Monoid. If someone does at a Ring class sometime, it is very likely to go into Data.Ring, which would lead to conflicts. In fact it already exists, see the monoids package [1] I would prefer the name RingList or CircularList. As long as you put the word ring in the package description users will still find it when searching on hackage. [1] http://hackage.haskell.org/packages/archive/monoids/0.1.25/doc/html/Data-Ring.html Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Transient monad
Alberto G. Corona wrote: Hi haskell cafe: concerning Stable Names The IO in makeStableName suggest more side effects than makeStableName really do. But still the call isn't pure. For calls such are makeStableName that gives a different result the FIRST time they are called but return the same result every time in the same session, I suggest to use a Transient monad: makeStableName doesn't really give 'the same result every time', though. For example: * let sn x = hashStableName $ makeStableName x * let x = replicate 3 'x' in (,) $ sn x * evaluate x * sn x (18,17) After x is evaluated in this example, its stable name changes. Perhaps instead of Transient we could use a name that makes it more clear what is going on, perhaps ObservingEvaluation. That could also include exception handling, by the way. makeStableName :: a - Transient (StableName a) Why not wrap it up in a class? class Monad m = MonadObservingEvaluation m where -- what should go here? perhaps: liftOE :: ObservingEvaluation a - m a Then we can have makeStableName :: MonadObservingEvaluation m = a - m (StableName a) Which works both in IO and the new monad. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative Functor or Idiom?
David Sankel wrote: After reading several recent papers I came to the understanding that there isn't consensus on the name of Applicative Functors. Several prefer to call them idioms: 'Idiom' was the name McBride originally chose, but he and Paterson now favour the less evocative term `applicative functor'. We have a slight preference for the former, not least because it lends itself nicely to adjectival uses, as in `idiomatic traversal'[1] I also noticed use of the term Idiom in [2], [3], and [4]. I much prefer the name Applicative Functor, because 'idiom' and especially 'idiomatic' can mean lots of other things (just look up the word in a dictionary!). While an applicative functor is always a functor with 'pure' and 'ap' operations. I'm writing a set of classes that includes AF's and I'm trying to decide whether to call the class Idiom. Anyone have more information on this question? Why are you writing your own? How do your classes differ from the standard Control.Applicative? Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Status of TypeDirectedNameResolution proposal?
Nicolas Pouillard wrote: The TDNR proposal really tries to do two separate things: 1. Record syntax for function application. The proposal is to tread x.f or a variation thereof the same as (f x) It is more like (ModuleToGuess.f x) than (f x). My point is that desugaring x.f to (f x) and treating some instances of (f x) as (ModuleToGuess.f x) are two separate things. In the current proposal these two are combined, but I see no reason to do so. To be a bit more concrete, I would propose: * General Type Directed Name Resolution (GTDNR): For every function application f x in the program where f is a name, f is resolved based on the type of the argument x. Note that I am not saying that this is necessarily a good idea, it is just a possible alternative to the current TDNR proposal. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Status of TypeDirectedNameResolution proposal?
Levi Greenspan wrote: What's the status of the TDNR proposal [1]? Personally I think it is a very good idea and I'd like to see it in Haskell'/GHC rather sooner than later. Working around the limitations of the current record system is one of my biggest pain points in Haskell and TDNR would be a major improvement. Thus I wonder if someone is actively working on this proposal? The TDNR proposal really tries to do two separate things: 1. Record syntax for function application. The proposal is to tread x.f or a variation thereof the same as (f x) 2. Type directed name lookup. The proposal is to look up overloaded names based on the type of the first function argument. Why can't these be considered separately? Is there a good reason for not using TDNR in normal function applications? The only argument I can think of (compared to the record syntax) is that it would be a bigger change. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fair diagonals
Sjoerd Visscher wrote:
I believe this does what you want:
code
The attached code should be more efficient, since it doesn't use integer
indices.
Note that this is just a 'level' monad: the list is stratified into levels, when
combining two levels, the level of the result is the sum of the levels of the
inputs.
map (map sum) . runDiags . traverse each $ [[1..], [1..], [1..]]
[[3],[4,4,4],[5,5,5,5,5,5],[6,6,6,6,6,6,6,6,6,6],[7,7,7,7,7,7,7,7,7,7,7,...
I looked on hackage but I was surprised that I couldn't find this simple monad.
The package level-monad does look very similar, only it uses a different list
type for the representation.
By the way, it seems Omega intentionally doesn't use this design. To quote the
documentation ... a breadth-first search of a data structure can fall short if
it has an infinitely branching node. Omega addresses this problem ...
Twan
-- A simple 'level' monad type
module MonadDiags where
import Control.Applicative
import Control.Monad
apD :: [[a - b]] - [[a]] - [[b]]
apD [] _ = []
apD _ [] = []
apD (xx:xs) ys = unionD (map apXX ys) ([] : apD xs ys)
where apXX yy = xx * yy
unionD :: [[a]] - [[a]] - [[a]]
unionD [] ys = ys
unionD xs [] = xs
unionD (x:xs) (y:ys) = (x++y) : unionD xs ys
-- Now to wrap things up in an applicative functor
newtype Diags a = Diags { runDiags :: [[a]] }
instance Functor Diags where
fmap f = Diags . map (map f) . runDiags
instance Applicative Diags where
pure a = Diags [[a]]
a * b = Diags (runDiags a `apD` runDiags b)
instance Alternative Diags where
empty = Diags [[]]
a | b = Diags (runDiags a `unionD` runDiags b)
each :: [a] - Diags a
each = Diags . map return
-- And if we want a monad, we should also have a join function
joinD :: [[Diags a]] - [[a]]
joinD [] = []
joinD (xx:xs) = unionsD (map runDiags xx) `unionD` ([] : joinD xs)
unionsD :: [[[a]]] - [[a]]
unionsD = foldr unionD []
instance Monad Diags where
return = pure
a = b = Diags (joinD (runDiags $ fmap b a))
fail _ = empty
instance MonadPlus Diags where
mzero = empty
mplus = (|)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Proposal: TypeDirectedNameResolution
John Meacham wrote: On Mon, Jul 27, 2009 at 04:41:37PM -0400, John Dorsey wrote: I'm assuming that name resolution is currently independent of type inference, and will happen before type inference. With the proposal this is no longer true, and in general some partial type inference will have to happen before conflicting unqualified names are resolved. My worry is that the proposal will require a compliant compiler to interweave name resolution and type inference iteratively. Indeed. This is my concern too. I can't see any way to do implement it in jhc at least without some major hassle. Name Resolution occurs several stages before typechecking, even before desugaring, having to intertwine it with type checking would be a complicated affair to say the least. You can still resolve the names first, while keeping the ambiguity: data Expr = ... | OverloadedVar [UniqueId] -- after name resolution Then the type checker checks all possible overloads, and in the end only one variable reference is left. TDNR would still complicate the typechecker, since it suddenly needs to do backtracking. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Float instance of 'read'
Mauricio wrote: Do you think 'read' (actually, 'readsPrec'?) could be made to also read the international convention (ie., read 1,5 would also work besides read 1.5)? I'm happy to finaly use a language where I can use words of my language to name variables, so I wonder if we could also make that step. That would be quite problematic in combination with lists, is read [1,2,3,4] == [1,2,3,4] or read [1,2,3,4] == [1.2, 3.4] Or something else? Localized reading should be somewhere else, perhaps related to Locales. As an aside, this is one of the (many) places where Haskell has made the right choice. In other languages such as Java input functions suddenly break when the user has a different locale setting. While for user input this might be desired, in my experience much of the i/o a program does is with well defined file formats where changing '.' to ',' just shouldn't happen. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad vs ArrowChoice
Ronald Guida wrote: I have read that Monad is stronger than Idiom because Monad lets me use the results of a computation to choose between the side effects of alternative future computations, while Idiom does not have this feature. Arrow does not have this feature either. ArrowChoice has the feature that the sum type, Either, can be used to choose between alternative computations, including their side effects. I know that Monad is supposed to be stronger than ArrowChoice, but I have to ask, what exactly can Monad do that ArrowChoice can't do? Monads are equivalent to ArrowApply, they allow you to use a computed *action*. For example: getMissileLauncher :: IO (String - IO ()) notWithArrows = do launchMissiles - getMissleLauncher launchMissiles Russia ArrowChoice is not enough to implement this function. But it is possible with ArrowApply, of which Kleisli IO is an instance. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] M1 + M2 = M3 where both computations in M1 and M2 can be used?
sam lee wrote: Hi. I want to compose two monads to build another monad where computations of the two monads can be used inside. I have: - MonadTypeInfer : interface (class) for TypeInfer monad - TypeInfer : a monad that has Map String Type (association of names and types) - TypeInferT : transformer of above monad - MonadEval : interface (class) for Eval monad - Eval : a monad that has Map String Expr (association of names and code/function body) - EvalT : transformer of Eval - tInfer :: Expr - TypeInfer Type -- given expr, returns type of it in TypeInfer monad - eval :: Expr - Eval Expr -- given expr, returns normalized expr in Eval monad Is there a way to build a monad where you could use sub-monads' (monads used to build current monad) computations? A solution to this problem is to use type classes, and in particular MonadTrans. You can then give an instance of MonadTypeInfer for EvalT m where m is an instance of MonadTypeInfer, and similarly an instance MonadEval for TypeInferT m. How this is implemented depends on the Monads in question, but if you use the monad transformer library with newtype deriving you can just add deriving MonadTrans. class Monad m = MonadTypeInfer m where -- functions -- tiStuff :: X - m Whatever class Monad m = MonadEval m where -- functions -- instance Monad m = MonadTypeInfer (TypeInferT m) where -- implementation -- tiStuff = ... instance Monad m = MonadEval (EvalT m) where -- implementation -- instance MonadEval m = MonadTypeInfer (EvalT m) where -- lift the functions from TypeInfer through the EvalT type, -- MonadTrans from the mtl might help here tiStuff x = lift (tiStuff x) tInfer :: MonadTypeInfer m = Expr - m Type eval :: MonadEval m = Expr - m Expr Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A commutative diagram conjecture about applicative functors
Isaac Dupree wrote: Unfortunately, I get puzzling type errors if I annotate either one of them with their type (e.g. (Applicative f) = f (a - b) - f a - f (Int, b) ) in an expression. The very answer doesn't seem to typecheck. :t \f x - fmap ((,) (0::Int)) (f * x) :: (Applicative f) = f (a1 - a) - f a1 - f (Int, a) Here the type annotation applies to the *body* of the lambda abstraction, adding parentheses around the whole thing solve your problem. :t (\f x - fmap ((,) (0::Int)) (f * x)) :: (Applicative f) = f (a1 - a) - f a1 - f (Int, a) Aside from the fact that ghci has some trouble formating the output. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A commutative diagram conjecture about applicative functors
Robin Green wrote: I am proving various statements relating to applicative functors, using the Coq proof assistant (I am considering only Coq terms, which always terminate so you don't have to worry about _|_). However, I'm not sure how to go about proving a certain conjecture, which, translated back into Haskell and made more specific to make it easier to think about, looks like this (assuming Control.Applicative and Control.Arrow are imported): For all applicative functors: \f x - fmap second f * fmap ((,) (0::Int)) x is equivalent to \f x - fmap ((,) (0::Int)) (f * x) Using the laws from the Control.Applicative haddock page, and some puzzling: First of all, to avoid getting lost in parenthesis hell, define: let g = (,) (0::Int) let c = (.) fmap second f * fmap g x law: fmap*2 = (pure second * f) * (pure g * x) law: composition = (pure c * (pure second * f)) * pure g * x law: interchange = pure ($g) (pure c * (pure second * f)) * x law: composition = pure c $ pure ($g) * pure c * (pure second * f) * x law: homomorphism*2 = pure (c ($g) c) * (pure second * f) * x simplify = pure (. g) * (pure second * f) * x law: composition = pure c * pure (. g) * pure second * f * x law: homomorphism*2 = pure (c (. g) second) * f * x rewrite (unpl) = pure (\ d u - (0,d u)) * f * x rewrite some more = pure (c g) * f * x law: homomorphism = pure c * pure g * f * x law: composition = pure g * (f * x) law: fmap = fmap g (f * x) Q.E.D. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is a type synonym declaration really a synonym ?
alpheccar wrote: Can someone confirm me that: type TA = A :+: B type TB = C :+: D type T = TA :+: TB This is type T = (A :+: B) :+: (C :+: D) is not equivalent to type T = A :+: B :+: C :+: D is type T = A :+: (B :+: (C :+: D)) So these types are indeed not the same. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Smart Constructor Puzzle
Ronald Guida wrote:
I'm playing around with smart constructors, and I have encountered a
weird puzzle.
My goal is to do vector arithmetic. I'm using smart constructors so
that I can store a vector as a list and use the type system to
staticly enforce the length of a vector.
So my first step is to define Peano numbers at the type level.
data PZero = PZero deriving (Show)
data PSucc a = PSucc a deriving (Show)
type P1 = PSucc PZero
type P2 = PSucc P1
type P3 = PSucc P2
-- etc
Next, I define a vector type and tag it with a Peano number.
data Vec s t = Vec [t] deriving (Eq, Ord, Show, Read)
Now I can define a few smart constructors.
vec0 :: Vec PZero t
vec0 = Vec []
vec1 :: t - Vec P1 t
vec1 x = Vec [x]
vec2 :: t - t - Vec P2 t
vec2 x y = Vec [x, y]
vec3 :: t - t - t - Vec P3 t
vec3 x y z = Vec [x, y, z]
Now here's the puzzle. I want to create a function vecLength that
accepts a vector and returns its length. The catch is that I want to
calculate the length based on the /type/ of the vector, without
looking at the number of elements in the list.
So I started by defining a class that allows me to convert a Peano
number to an integer. I couldn't figure out how to define a function
that converts the type directly to an integer, so I am using a
two-step process. Given a Peano type /t/, I would use the expression
pToInt (pGetValue :: t).
class Peano t where
pGetValue :: t
pToInt :: t - Int
instance Peano PZero where
pGetValue = PZero
pToInt _ = 0
instance (Peano t) = Peano (PSucc t) where
pGetValue = PSucc pGetValue
pToInt (PSucc a) = 1 + pToInt a
Finally, I tried to define vecLength, but I am getting an error.
vecLength :: (Peano s) = Vec s t - Int
vecLength _ = pToInt (pGetValue :: s)
Could not deduce (Peano s1) from the context ()
arising from a use of `pGetValue'
Possible fix:
add (Peano s1) to the context of the polymorphic type `forall s. s'
In the first argument of `pToInt', namely `(pGetValue :: s)'
In the expression: pToInt (pGetValue :: s)
In the definition of `vecLength':
vecLength _ = pToInt (pGetValue :: s)
Any suggestions?
The type 's' is not available outside the type signature. There is an
extension, ScopedTypeVariables that does just this, allowing you to write:
{-# LANGUAGE ScopedTypeVariables #-}
vecLength :: forall s. (Peano s) = Vec s t - Int
vecLength _ = pToInt (pGetValue :: s)
An alternative is to use a 'fake' function to force a value to be of type s
vecLength :: (Peano s) = Vec s t - Int
vecLength v = pToInt (phantomType v)
phantomType :: Vec s t - s
phantomType = undefined
Also, undefined and type signatures are the key to writing short classes in
these situations:
class ToInt a where
toInt :: a - Int
instance ToInt PZero where
toInt _ = 0
instance ToInt a = ToInt (PSucc a) where
toInt _ = toInt (undefined :: a) + 1
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list utilities -- shouldn't these be in the hierarchical libs somewhere?
Jules Bean wrote: Thomas Hartman wrote: I found http://haskell.cs.yale.edu/haskell-report/List.html had many useful one off type list functions such as subsequences and permutations which are nowhere to be found in hoogle, Data.List, or the haskell hierarchical libs Weird. It's not very many. Other that those, I spotted: sums, products, elemIndexBy, elemBy. I have no idea why they were removed between that version of the report and haskell98. For the ones you mention: - sums, products: The names don't make it clear what they do, I could for instance imagine sums being 'map sum'. And should it be a 'scanl' or 'scanr'? - elemIndexBy, elemBy: elemBy f x = any (f x) elemIndexBy f xs x = findIndex (f x) xs On the other hand, I would love to see subsequences and permutations added to Data.List. In fact, I made a library proposal to make this happen, hopefully they will be added to the standard library soon. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] class default method proposal
Simon Peyton-Jones wrote: Concerning (b) here's a suggestion. As now, require that every instance requires an instance declaration. So, in the main example of http://haskell.org/haskellwiki/Class_system_extension_proposal, for a new data type T you'd write instance Monad T where return = ... (=) = ... instance Functor T instance Applicative T Another alternative is to allow multiple classes in an instance declaration: instance (Monad T, Functor T, Applicative T) where return = ... (=) = ... The advantage is that this makes it more clear where the instances come from, especially if a class has multiple sub classes with different defaults. It also eliminates tricky issues with importing. Of course this needs some (albeit very little) new syntax. I wrote a proposal a while ago, http://haskell.org/haskellwiki/Superclass_defaults Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Showing Data.Ratio - different on GHC vs Hugs/Yhc
Neil Mitchell wrote: Hi Under Hugs and Yhc, showing a Ratio 1%2 gives 1 % 2. Under GHC showing 1%2 gives 1%2. Does the standard say anything about this? Is someone wrong? Yes, ghc is wrong here, the Haskell 98 report [1] specifies: instance (Integral a) = Show (Ratio a) where showsPrec p (x:%y) = showParen (p ratPrec) (showsPrec (ratPrec+1) x . showString % . showsPrec (ratPrec+1) y) While it doesn't really matter, it is a deviation from the standard. I would personally prefer it if rationals were shown as 1%2, because the space is not needed, and other show instances such as lists don't insert spaces either. [1]: http://haskell.org/onlinereport/ratio.html Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Transformation sequence
Andrew Coppin wrote: I'm writing some code where I take an expression tree and transform it into another equivilent one. Now it's moderately easy to write the code that does the transformation. But what I *really* want is to print out the transformation *sequence*. This appears to be much more awkward. What I have is a function like this: transform :: Expression - [Expression] The trouble is, if you want to apply the transformation recursively, things get very messy. Oh, it *works* and everything. It's just really messy and verbose. In Haskell, this is usually a sign that you want to start applying some ingenious trickery... but I'm having an ingeniety failure here. Suppose, for example, that in one case you want to recursively transform two subexpressions. I end up writing something like transform (...sub1...sub2...) = let sub1s = transform sub1 sub2s = transform sub2 in map (\sub1' - put sub1' back into main expression) sub1s ++ map (\sub2' - put sub2' back into main expression) sub2s After you've typed that a few times, it becomes *very* boring! But I can't think of a clean way to abstract it. :-( It's *almost* like you want to use the list monad: transform (...sub1...sub2...) = do sub1' - transform sub1 sub2' - transform sub2 return (put sub1' and sub2' back into the main expression) How about: transform ... = (transform sub1 = put back into main expression) ++ (transform sub2 = put back into main expression) Or something to that effect? Or maybe transform ... = do sub' - transform sub1 ++ transform sub2 put back into main expression) It would help if you gave some more information on what 'put back into main expression' actually looks like. A trick I often find useful when working with transformations is to have a function step :: Expression - Maybe Expression that applies a single transformation step, and returns Nothing if no further transformations are possible. You then use the maybe monad, and run steps with: runSteps :: (a - Maybe a) - a - a Alternatively, the intermediate results could be remebered, then the function would return a list instead. For combining alternatives you can define orElse :: (a - Maybe a) - (a - Maybe a) - (a - Maybe a) Again, I am not sure if any of this applies to your problem, but it might help. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: PROPOSAL: New efficient Unicode string library.
Lots of people wrote: I want a UTF-8 bikeshed! No, I want a UTF-16 bikeshed! What the heck does it matter what encoding the library uses internally? I expect the interface to be something like (from my own CompactString library): fromByteString :: Encoding - ByteString - UnicodeString toByteString :: Encoding - UnicodeString - ByteString The only matter is efficiency for a particular encoding. I would suggest that we get a working library first. Either UTF-8 or UTF-16 will do, as long as it works. Even better would be to implement both (and perhaps more encodings), and then benchmark them to get a sensible default. Then the choice can be made available to the user as well, in case someone has specifix needs. But again: get it working first! Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] PROPOSAL: New efficient Unicode string library.
Johan Tibell wrote: Dear haskell-cafe, I would like to propose a new, ByteString like, Unicode string library which can be used where both efficiency (currently offered by ByteString) and i18n support (currently offered by vanilla Strings) are needed. I wrote a skeleton draft today but I'm a bit tired so I didn't get all the details. Nevertheless I think it fleshed out enough for some initial feedback. If I can get the important parts nailed down before Hackathon I could hack on it there. Apologies for not getting everything we discussed on #haskell down in the first draft. It'll get in there eventually. Bring out your Unicode kung-fu! http://haskell.org/haskellwiki/UnicodeByteString Have you looked at my CompactString library[1]? It essentially does exactly this, with one extension: the type is parameterized over the encoding. From the discussion on #haskell it would seem that some people consider this unforgivable, while others consider it essential. In my opinion flexibility should be more important, you can always restrict things later. For the common case where encoding doesn't matter there is Data.CompactString.UTF8, which provides an un-parameterized type. I called this type 'CompactString' as well, which might be a bit unfortunate. I don't like the name UnicodeString, since it suggests that the normal string somehow doesn't support unicode. This module could be made more prominent. Maybe Data.CompactString could be the specialized type, while Data.CompactString.Parameterized supports different encodings. A word of warning: The library is still in the alpha stage of development. I don't fully trust it myself yet :) [1] http://twan.home.fmf.nl/compact-string/ Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Accumulator value for and and or
PR Stanley wrote: Hi or = foldl (||) False and = foldl () True I can understand the rationale for the accumulator value - True [] where [] = True and True || [] where [] = False Other than the practical convenience is there a reason for having the empty list in and and or equating to True and False? Thanks, Paul Another way to think about this is to look at any p = or . map p all p = and . map p Now, all even [] should hold, since everything in that list is even. But not any even [] because there is no even number in the empty list. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Extending the idea of a general Num to other types?
Bulat Ziganshin wrote: Hello Simon, Wednesday, September 5, 2007, 11:19:28 AM, you wrote: when you come across a case where GHC produces an unhelpful message, send it in, along with the program that produced it, i have put such tickets about year ago :) basically, it was about just changing wording: instead of inferred write: Expected type: ... Actual type: ... This doesn't help enough. What is an 'expected' type? How is it not 'actual'? I want it to be immediatly clear which type is which. Say I write x ++ 'y' Right now the error is Couldn't match expected type `[Char]' against inferred type `Char' In the second argument of `(++)', namely 'y' What always confuses me is which of these two types is the parameter I gave, and which is the one expected by the function? Changing 'infered' to 'actual' is an improvement, but it is not enough. I would suggest: (++) expects second argument to be of type '[Char]' but was given 'y' of type 'Char' Anothing thing that would be useful is *why* (++) expects a certian type, say I enter x ++ [1::Int] Instead of the above, the following would be more useful: the function (++) has type: [a] - [a] - [a] the first argument suggests: a = Char the second argument suggests: a = Int Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC optimisations
Stefan O'Rear wrote: On Wed, Aug 22, 2007 at 06:36:15PM +0100, Neil Mitchell wrote: Hi If Num obeys ring axioms, fromInteger is a perfectly fine ring-homomorphism. (It's also the first or second homomorphism taught.) Does Int obey these axioms? I'm thinking that assuming properties about things such as numbers is very likely to go wrong very quickly. Monads you might be able to get away with, Numbers you probably can't. Int does obey the axioms, it's the classical ring ℤ[4294967296]. Double, however, does not: But Double is already quite badly behaved: let x = 1e20 Prelude 1 + (x - x) 1.0 Prelude (1 + x) - x 0.0 Using the fromInteger (and fromRational) axioms should only *increase* precission, I don't see how that is such a bad thing. Also, as far as I can see GHC already does this optimizations if the type is specialized to Double. Except for the fact that the PrelRules rules don't seem to fire, because the constants get floated out. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC optimisations
Isaac Dupree wrote:
Simon Peyton-Jones wrote:
...
No, constant folding is part of the compiler, I'm afraid, in the
module PrelRules.
Simon
_Constant_ folding is, but in GHC.Base there are rules like (unboxed)
multiplying by zero or one, or adding or subtracting zero, from an
unknown other (non-constant) value. I think shifts might be doable via
RULES... if you were willing to make one rule for each denominator 2, 4,
8 and so on, which rather depends on max. Int... (and that's not
Integers either, I guess)
Just to see what this would look like.
First of all, optimizing mod and div can not be done with PrelRules,
because they are not primitives, quot and rem are. And most of the nice
optimizations with shifts no longer work there. But using rules should
work, assuming the inliner is not too fast.
Multiplication and division can become shifts:
{-# RULES
-- x * 2^n -- x `shiftL` n
x# *# 2# forall x#. x# *# 2# = x# `iShiftL#` 1#
2# *# x# forall x#. 2# *# x# = x# `iShiftL#` 1#
-- etc.
-- x `div` 2^n -- x `shiftR` n
x# `divInt#` 2# forall x#. divInt# x# 2# = x# `iShiftRA#` 1#
x# `divInt#` 4# forall x#. divInt# x# 4# = x# `iShiftRA#` 2#
-- etc.
Mod can become and:
-- x `mod` 2^n -- x .. (2^n - 1)
x# `modInt#` 2# forall x#. modInt# x# 2# = andInt# x# 1#
x# `modInt#` 4# forall x#. modInt# x# 4# = andInt# x# 3#
-- etc.
#-}
Here I use a new function (see instance Bits Int),
andInt# :: Int# - Int# - Int#
andInt# x# y# = word2Int# (int2Word# x# `and#` int2Word# y#)
but you could write that inline as well.
A problem with these rules is that you need a whole lot of them. 32 per
operation (on a 32 bit platform), * 4 operations, * 2 separate versions
for words and ints = 256.
Other rules that could be interesting are:
forall a b. fromInteger a + fromInteger b = fromInteger (a + b)
forall a b. fromInteger a * fromInteger b = fromInteger (a * b)
-- etc.
To allow optimizations on generic Num code, although I am not sure what
the Haskell spec has to say about this.
Now, if you want to get really creative you can use other semi-evil
optimization tricks for quot and rem.
The following is based on code generated by Visual C++:
-- remPowInt x y == x `rem` (2^y)
remPowInt x y
| r = 0 = r
| otherwise = ((r - 1) .|. (complement yWithSign)) + 1
where r = x .. yWithSign
yWithSign = (1 `shiftL` (bitSize - 1)) .|.
((1 `shiftL` y) - 1)
Or in assembly (for y == 2, so x `rem` 4)
and ecx,8007h
jns main+60h (401060h)
dec ecx
or ecx,0FFF8h
inc ecx
The C++ compiler also performs other optimizations when multiplying with
other constants, for example *3 becomes something like
lea eax, [eax+eax*2]
Divisions become horrendous constructs with magic numbers,
-- eax := ecx / 5
mov eax,6667h
imulecx
sar edx,1
mov eax,edx
shr eax,1Fh
add eax,edx
But such things are probably best left to the code generator / a
peephole optimizer, if they are done at all. I think the LEA trick
should be feasible.
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC optimisations
Brandon S. Allbery KF8NH wrote: On Aug 21, 2007, at 22:13 , Twan van Laarhoven wrote: Other rules that could be interesting are: forall a b. fromInteger a + fromInteger b = fromInteger (a + b) I don't think this will work, a and b have to be the same type. They are of the same type, both are Integers, forall a b :: Integer. ((fromInteger (a::Integer)) + (fromInteger b)) :: Num n = n = (fromInteger (a + b :: Integer)) :: Num n = n Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Chessboard-building in Haskell
Andrew Wagner wrote:
I've started a blog series on writing a chess engine in Haskell. I
just posted the second blog entry today:
http://sequence.complete.org/node/361
I suspect there's more work to be done on that function, though. It
seems like there should be a nice way to remove that flip in apply.
Any thoughts?
The trick is that you should always prefer zipWith over zip if you have
the chanse, tuples make life harder.
Let's use some equational reasoning:
foldl apply emptyGameState (zip funcs fields)
= {- fill in 'apply' -}
foldl (flip (ap fst snd)) emptyGS (zip funcs fields)
= {- write it as a lambda function to make it clearer -}
foldl (\y (f,x) - f x y) emptyGS (zip funcs fields)
= {- split fold into a fold and a map -}
foldl (\y fx - fx y) emptyGS $ map (\(f,x) - f x)
$ (zip funcs fields)
= {- map . zip -- zipWith -}
foldl (\y fx - fx y) emptyGS $ zipWith (\f x - f x) funcs fields
= {- use prelude functions -}
foldl (flip ($)) emptyGS $ zipWith ($) funcs fields
~= {- now, do you really want a foldl or will foldr do? -}
foldr ($) emptyGS $ zipWith ($) funcs fields
You can now also write the function in pointfree style:
loadFEN = foldr ($) emptyGameState
. zipWith ($) funcs
. words
where funcs = [parseBoard, parseCastleStatus]
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How do I simulate dependent types using phantom types?
DavidA wrote: Hi, I am trying to implement quadratic fields Q(sqrt d). These are numbers of the form a + b sqrt d, where a and b are rationals, and d is an integer. ... class IntegerType a where value :: Integer The problem is, this doesn't work. GHC complains: The class method `value' mentions none of the type variables of the class IntegerType a When checking the class method: value :: Integer In the class declaration for `IntegerType' Is what I'm trying to do reasonable? If no, what should I be doing instead? If yes, why doesn't GHC like it? You are on the right track. The problem with the class method is that it doesn't use type 'a' anywhere, consider f :: Integer f = value What class instance should be used here? The solution is to use a dummy parameter: class IntegerType a where value :: a - Integer And call it like: f = value (undefined :: Two) So for instance: instance IntegerType d = Show (QF d) where show (QF a b) = show a ++ + ++ show b ++ sqrt ++ show (value (undefined::d)) The problem is that this doesn't work, because d is not in scope, you need the scoped type variables extension: valueOfQF :: forall a. IntegerType a = QF a - Integer valueOfQF qf = value (undefined :: a) or maybe better, change the class: class IntegerType a where value :: QF a - Integer Now you can simply use instance IntegerType d = Show (QF d) where show qf@(QF a b) = show a ++ + ++ show b ++ sqrt ++ show (value qf) Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Re: Re: monad subexpressions
Antoine Latter wrote: On 8/3/07, Chris Smith [EMAIL PROTECTED] wrote: Yes, unless of course you did: instance (Monad m, Num n) = Num (m n) or some such nonsense. :) I decided to take this as a dare - at first I thought it would be easy to declare (Monad m, Num n) = m n to be an instance of Num (just lift or return the operators as necessary), but I ran into trouble once I realized I needed two things I wasn't going to get: An instance of Eq (m n), and an instance of Show (m n) for all monads m. Eq would need a function of the form: (==) :: Monad m = m a - m a - Bool and Show would need a function of type m a - String What about Eq1 and Show1 classes? In the same vein as Typeable1: class Eq1 f where eq1 :: Eq a = f a - f a - Bool neq1 :: Eq a = f a - f a - Bool class Show1 f where show1 :: Show a = f a - String showsPrec1 :: Show a = Int - f a - ShowS Now you can declare the Num instance: instance (Monad m, Eq1 m, Show1 m, Num n) = Num (m n) where (+) = liftM2 (+) (-) = liftM2 (-) (*) = liftM2 (*) abs = liftM abs signum = liftM signum negate = ligtM negate fromInteger = return . fromInteger And just to show that such instances can exist: instance Eq1 [] where eq1 = (==) neq1 = (/=) instance Show1 [] where show1 = show showsPrec1 = showsPrec Note: All of this is untested code. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Read-only functions in State Monad
Ken Takusagawa wrote: I'd like to have a state monad with the feature that I can somehow annotate using the type system that some functions are only going to read the state and not modify it. Such read-only functions are only permitted to call other read-only functions, whereas state-modifying functions can call both read-only and other state-modifying functions. How can I do this? It does not seem to be straightforwardly doable with Control.Monad.State. How about something like readonly :: Reader a - State a readonly = gets . runReader Implicit conversion is probably not possible with Control.Monad.State, you will have to make your own monad, maybe newtype State2 w s a = State2 (State s a) data Write The phantom type w can be used to encode whether writing is needed (State2 Write) or not (forall w. State2 w) get :: State2 w s s put :: s - State2 Write s s Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Disadvantages of de Bruijn indicies?
Neil Mitchell wrote: Hi, de Bruijn indicies look quite nice, and seem to eliminate a lot of complexity when dealing with free variables: http://en.wikipedia.org/wiki/De_Bruijn_index So I was wondering, are they suitable for use in a compiler? If so, what are their disadvantages/advantages? Is there any particular reason that GHC (as an example) doesn't use them in its Core? I'm trying to decide if I should use them in my compilers data type - and would like some recommendations before I start. Thanks The bigest advantage of De Bruijn indices are that: - alpha conversion is not needed and comparison is always modulo renaming. - inlining is very easy I think the largest disadvantage (asside from readability) is that you lose the ability to use a Map as a symbol table for local information (since the names change with each level). Another mayor disadvantage is that it is not immediatly clear how to use De Bruijn numbers with recursive let bindings and case branches, since a single node binds multiple variables. In my toy theorem prover code I use pairs of numbers to solve this, the first is the normal De Bruijn index, the second gives an index into the list of declarations. I believe the Epigram compiler uses De Bruijn numbers for its core language. Have a look at I am not a number: I am a free variable by Conor McBride and James McKinna, http://www.e-pig.org/downloads/notanum.pdf Their approach is based on a Scope datatype: data Scope a = Name :. a Which is used to 'remember' the names of bound variables. This will allow you to largely restore the readability. Another advantage is that code dealing with scoping can be localized. One final thing I noticed is that a lot of the advantages of De Bruijn numbers disappear if expressions you operate on can have free variables. Say you want to beta reduce (a b), but b contains free variables (in the form of De Bruin indices), now you can no longer just substitute b in a; you have to increment all the indices of the free variables for each scope you enter in a, so these variables are not accedentially captured by that scope. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Recent content is available under a simple permissive license
Robin Green wrote: The Haskell wiki[1] says Recent content is available under a simple permissive license. But this is unilluminating - recent? how recent, exactly? - and will become increasingly understated as time goes by. Wouldn't it be slightly more helpful to say Content added after ... /MM/DD ... is available under a simple permissive license? Clicking that link (http://haskell.org/haskellwiki/HaskellWiki:Copyrights) leads to a page that says: Contributions since 2006-01-14 05:15 UTC are available under the above license. But you are right that 'recent' is not really the right term, are there other suggestions? Of course the best solution would be to fix the license on all things added before 2006-01-14... Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Morphing ASTs and scrapping boilerplate code
Joel Reymont wrote: I have a lot of boilerplate code like this and wonder how I can scrape it. instance Morpher Type C.Type where morph TyInt = return C.TyInt morph TyFloat = return C.TyFloat morph TyStr = return C.TyStr morph TyBool = return C.TyBool morph TyColor = return C.TyColor morph TyStyle = return C.TyStyle morph (TyList ty) = liftM C.TyList (morph ty) morph (TyArray ty) = liftM C.TyArray (morph ty) morph (TySeries ty) = liftM C.TySeries (morph ty) morph (TyInput ty) = liftM C.TyProp (morph ty) morph (TyRef ty) = liftM C.TyRef (morph ty) morph TyUnit = return C.TyUnit morph TyPrintDest = return C.TyPrintDest One option is to change your data types. I would suggest something like this: data Type = TyPrim TyPrim | TyCon TyCon Type data C.Type = C.TyPrim TyPrim | C.TyCon TyCon C.Type where TyPrim and TyCon (primitves and constructors) can be shared: data TyPrim = TyInt | TyString | TyFloat | TyBool | etc. data TyCon = TyList | TyArray | TySeries | TyInput | TyRef Now the class instance can be: instance Morpher Type C.Type where morph (TyPrim p) = return (C.TyPrim p) morph (TyCon c t) = C.TyCon c $ morph t -- or liftM for people not so in love with Applicative :) Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic derivation (TemplateHaskell?)
Joel Reymont wrote: This is in Language.Haskell.TH.Syntax which is imported at the top of Data/Derive/TH.hs so I don't understand the cause of the error instance Functor Q where fmap f (Q x) = Q (fmap f x) ... Any suggestions? Since Q is a Monad, you can make the instance instance Functor Q where fmap = liftM But Q is exported by Languave.Haskell.TH.Syntax !!! Only the type constructor is exported, not the data constructor. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Duplicate instance declaration
Bas van Dijk wrote: I would also like to get the formatting constraints working. However the solution in the code below gives a Duplicate instance declarations error. If I -fallow-overlapping-instances than the type checker goes into an infinite loop. I would like to know why this is happening and if there's a way to fix it. You have multiple instances with the same instance head (the part after the =). Haskell doesn't look at the context when deciding what instance to use, so they overlap. An alternative idea would be to use data types instead of classes for the registers and memory locations data Reg size tag = Reg data EAX_ -- dummy type, not exported -- only export this type EAX = Reg Bit32 EAX_ eax :: EAX eax = Reg and similairly for memory data Mem size tag = Mem Word32 data Mem32_ -- dummy type, not exported type Mem32 = Mem Bit32 Mem32_ Now you can have the instances instance MovFormat (Reg size a) (Reg size b) instance MovFormat (Reg size a) (Mem size b) etc. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Consequences of newtype deriving implementation w.r.t. base classes
I just noticed some unexpected consequences of the way newtype deriving
is implemented in GHC. Because the dictionary of the underlying type is
reused, so are base classes. This message is a literate Haskell program
illustrating the problem.
{-# OPTIONS_GHC -fglasgow-exts #-}
This problem comes up when an instance method calls a method of a base
class. Consider the following useless example:
class Show a = Show2 a where
show2 :: a - String
show2 = show
instance Show2 Int
Now consider a type deriving Show2, but having a different
implementation of Show (also derived).
newtype Meter = Meter Int
deriving (Eq, Show, Show2)
Now, for show2 the derived Show instance (which also shows the
constructor name) is *not* used, instead the Show Int instance is used:
] show2 (Meter 1)
] 1
] show (Meter 1)
] Meter 1
This is quite unexpected, unless you consider what is going on behind
the scenes. Even more confusingly, GHC requires that there is a Show
instance for Meters, even if it will not be used!
]No instance for (Show Meter)
] arising from the superclasses of an instance declaration at ...
]Probable fix: add an instance declaration for (Show Meter)
]In the instance declaration for `Show2 Meter'
This problem can come up whenever a class instance uses a function from
a base class. Right now this not likely happen, but it will become more
common if the standard classes are split up:
class Additive a where
add :: a - a - a
class Additive a = Subtractive a where
neg :: a - a
sub :: a - a - a
sub x y = add x (neg y) -- calls base class function add
class Functor m = Monad' m where
return' :: a - m a
join' :: m (m a) - m a
join' x = bind' x id
bind' :: m a - (a - m b) - m b
bind' ma k = join' (fmap k ma) -- calls base class function fmap
As a solution I would suggest that newtype deriving a class instance is
only allowed if all base classes instances are also derived using
newtype deriving. This presents problems for Show and Read, because they
cannot be derived in that way. It will, however, catch problems with
most other classes.
Twan van Laarhoven
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementation of scaled integers
Stefan Heinzmann wrote: Hi all, is there a library for Haskell that implements scaled integers, i.e. integers with a fixed scale factor so that the scale factor does not need to be stored, but is part of the type? Data.Fixed [1] does exactly that, only it is based on Integer. Using fixed point with finite sized integers is more tricky, because you have to be careful not to get overflows in intermediate results. Twan [1] http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Fixed.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] foreach
Couldn't '\' delimit a subexpression, as parentheses do? Would there be
any ambiguity in accepting code like State \s - (s, s) instead of
requiring State $ \s - (s, s), or taking
Looking at the Haskell 98 language definition it seems that a whole
class of these expressions are disallowed inside function applications:
exp10 - \ apat1 ... apatn - exp
| let decls in exp
| if exp then exp else exp
| case exp of { alts }
| do { stmts }
| fexp
This means that none of the following are legal Haskell declarations,
even though they are unambiguous:
a = State \s - (s, s)
b = map let f x = x + 1 in f
c = return if a then b else c
d = catch do x - getLine
return x
It can be argued that this is mostly obfuscation, and that it can
sometimes be confusing, especially with let and do, but it saves on the
amount of parentheses or $s. What was the original reasoning for
disallowing these more complex expressions as the rightmost argument in
an fexp? Or was this simply not considered?
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] MonadList?
Michael Shulman wrote: The frequent occurence of ListT $ return in my code when I use the ListT monad transformer has made me wonder why there isn't a standard typeclass `MonadList', like those for the other monad transformers, encapsulating the essence of being a list-like monad -- in this case, the ability to select from a list of things. I quickly wrote one for myself: class MonadList m where option :: [a] - m a Another use for this class is for selecting a random option: instance MonadList SomeMonadWithRandomness where option os = pos - randomRM (0, length os - 1) return (os !! pos) It can also be used for the Nondet monad described in http://haskell.org/hawiki/NonDeterminism, and as a replacement for the Parsec combinator 'choice' (which IMHO is a better name). Although msum might suffice in these cases. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
Magnus Jonsson wrote: Dear Haskell Cafe, When programming the other day I ran into this problem. What I want to do is a function that would work like this: splitStreams::Ord a=[(a,b)]-[(a,[b])] splitStreams [(3,x),(1,y),(3,z),(2,w)] [(3,[x,z]),(1,[y]),(2,[w])] A O(n log(n)) algorithm is easy if you use Data.Map: import qualified Data.Map as Map splitStreamsMap :: Ord a = [(a,b)] - Map.Map a [b] splitStreamsMap = foldl add Map.empty where add (a,b) m = Map.insertWith (++) a [b] splitStreams = Map.fromList . splitStreamsMap Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
Jared Updike wrote: Wouldn't you want the expression [[1,0],[0,2]] + 10 to yield [[11,10],[10,12]] You could handle this as a special case in (+) and (*), but this is kind of a hack. Something like: (+) [[x]] y = map (map (x+)) y (+) x [[y]] = map (map (+y)) x (+) xy = zipWith (zipWith (+)) x y Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] QuickChecking IO
Mike Gunter wrote: I'd like to use QuickCheck on IO code. For instance, I'd like to check a property of type String - IO Bool. Using unsafePerformIO seems straightforward (though I haven't written the code, so I may be wrong about that) and it might be possible to make a solution involving unsafeInterleaveIO work. Short of rewriting QuickCheck, is there any way to check IO code safely? To use QuickCheck on IO you would need an instance of Arbitrary that can generate arbitrary states of the world :) If you ignore that you could, for example, make tests that depends on some files existing outside the program. To me that sounds like a bad idea, or at least outside the realm of QuickCheck. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] CDouble type coercion
SevenThunders wrote:
test.hs:14:11:
No instance for (PrintfType (t t1))
arising from use of `printf' at test.hs:14:11-16
Probable fix: add an instance declaration for (PrintfType (t t1))
In the result of a 'do' expression: printf %14.7g u
In the definition of `test': test = do printf %14.7g u
Failed, modules loaded: none.
The problem here appears to be the monomorphism restriction. This means
that all declarations without arguments get a monomorphic type, a type
without variables. The type of 'test' would be 'PrintfType r = r', but
the compiler does not allow this type. The solution is to either:
- make the type explicit by adding a type declaration, test :: IO ()
or Test :: PrintfType r = r
- make test local in a context where it is only used as an IO action,
for example:
main :: IO ()
main = do {... ; test ; ...}
where test = printf %14.7g 3.14
- add a parameter to test
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial Derivatives
Gerhard Navratil wrote: I need a library that provides partial derivatives for functions. The solution I came up with is based on a datatype using reversed polish notation to store the function: lots of code The solution works but is not very elegant. The complete module is appended to the mail. Does anyone have a more elegant solution or is there a package that provides derivatives in a similar way? A simple way to make it more ellegant is to use smart constructors, so you don't have to check to prevent zeroes everywhere: sub :: Fkt a - Fkt a - Fkt a sub a b | b == 0= a | a == 0= Neg b | otherwise = Sub a b -- etc. Now you can use this smart constructor instead of the real constructor without worry, like: derivative name (Sub a b) = sub (derivative name a) (derivative name b) -- etc. Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
