headers
wren ng thornton | 1 Mar 2012 04:45

ANN: stm-chans 1.3.1

--------------------------------------------
-- stm-chans 1.3.1
--------------------------------------------

The stm-chans package offers a collection of channel types, similar to 
Control.Concurrent.STM.TChan but with additional features.

--------------------------------------------
-- Changes (since 1.2.0)
--------------------------------------------

* (Version 1.3.1) The new stm-2.3 has finally been released with all the 
new optimized operations on TVars, TMVars, and TChans. I've updated the 
CPP macros in the Compat modules so that now they will actually switch 
over to the optimized implementations (instead of waiting for stm-9.0 :) 
It's highly recommended that all users bump their minimum stm-chans 
requirement to version 1.3.1.

* (Version 1.3.0) Added Control.Concurrent.STM.TMVar.Compat for the 
stm-2.3 function tryReadTMVar.

--------------------------------------------
-- Long description
--------------------------------------------

In particular stm-chans offers these types:

* Control.Concurrent.STM.TBChan:  Bounded FIFO channels.

     When the channel is full, writers will block/retry. This ensures
(Continue reading)

Permalink | Reply | 0 comments |
headers
Bas van Dijk | 1 Mar 2012 09:31
Picon
Gravatar

Re: Functor instance for Set?

On 29 February 2012 19:54, Daniel Gorín <dgorin <at> dc.uba.ar> wrote:
> I was always  under the impression that the fact that Data.Set.Set can not be made an instance of Functor
was a sort of unavoidable limitation.

I guess the way forward is to start using ConstraintKinds and TypeFamilies:

{-# LANGUAGE ConstraintKinds, TypeFamilies, FlexibleInstances #-}

import Prelude hiding (Functor, fmap)
import Data.Set (Set)
import qualified Data.Set as Set (map)
import GHC.Exts (Constraint)

class Functor f where
    type FunctorConstraint f :: * -> Constraint
    type FunctorConstraint f = Empty

    fmap :: (FunctorConstraint f b) => (a -> b) -> f a -> f b

class Empty a
instance Empty a

instance Functor Set where
    type FunctorConstraint Set = Ord
    fmap = Set.map

    -- Note that the unnecessary 'Ord a' constraint needs to be dropped from:
    -- Set.map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

Regards,
(Continue reading)

Permalink | Reply | 4 comments |
headers
Daniel Gorín | 1 Mar 2012 09:33
Picon
Favicon

Re: Functor instance for Set?

On Feb 29, 2012, at 8:21 PM, Twan van Laarhoven wrote:

> On 2012-02-29 19:54, Daniel Gorín wrote:
>> Hi
>> 
>> ...
>> 
>> It appears to me, then, that if "Set a" were implemented as the sum of a list
>> of a and a BST, it could be made an instance of Functor, Applicative and even
>> Monad without affecting asymptotic complexity (proof of concept below). Am I
>> right here? Would the overhead be significant? The one downside I can think
>> of is that one would have to sacrifice the Foldable instance.
> 
> A problem is that you lose complexity guarantees. Consider for example:
> 
>    let ints = [0..1000000]
>    let setA = Set.fromList ints
>    let setB = fmap id setA
>    let slow = all (`Set.member` setB) ints
> 
> Each call to Set.member in slow will take O(n) instead of the expected O(log n), which means that this code
takes O(n^2) instead of O(n*log n). The problem is that you keep converting the same set from a list to a tree
over and over again.

Right, good point, updating a set after an fmap is ok, but querying is not. What one would need, then, is
querying the set to have also the side-effect of updating the internal representation, from [a] to BST.
This seems doable using an IORef and unsafePerformIO (example below). It is ugly but still referentially
transparent (I think). Would this work in practice?

Daniel
(Continue reading)

Permalink | Reply | 0 comments |
headers
Daniel Gorín | 1 Mar 2012 10:19
Picon
Favicon

Re: Functor instance for Set?

On Thu, 2012-03-01 at 09:31 +0100, Bas van Dijk wrote:
> On 29 February 2012 19:54, Daniel Gorín <dgorin <at> dc.uba.ar> wrote:
> > I was always  under the impression that the fact that Data.Set.Set can not be made an instance of Functor
was a sort of unavoidable limitation.
> 
> I guess the way forward is to start using ConstraintKinds and TypeFamilies: [...]

This doesn't really solve the problem I was looking at (namely, making
an ordered-tree-based implementation of a Set type an instance of the
standard Functor class) but I find it very interesting nevertheless. I
need to look at this ConstraintKinds extension in more detail....

Thanks,
Daniel

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Permalink | Reply | 0 comments |
headers
Twan van Laarhoven | 1 Mar 2012 13:20
Picon
Gravatar

Re: Functor instance for Set?

On 01/03/12 09:31, Bas van Dijk wrote:
> class Functor f where
>      type FunctorConstraint f :: * ->  Constraint
>      type FunctorConstraint f = Empty
>
>      fmap :: (FunctorConstraint f b) =>  (a ->  b) ->  f a ->  f b
>
> class Empty a
> instance Empty a

Do you really need this Empty class? That seems inconvenient. I had 
hoped you would be able to write something like

     type FunctorConstraint f :: * ->  Constraint
     type FunctorConstraint f a = ()

Twan
Permalink | Reply | 2 comments |
headers
Gábor Lehel | 1 Mar 2012 14:26
Picon

Re: Functor instance for Set?

On Thu, Mar 1, 2012 at 1:20 PM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:
> On 01/03/12 09:31, Bas van Dijk wrote:
>>
>> class Functor f where
>>     type FunctorConstraint f :: * ->  Constraint
>>     type FunctorConstraint f = Empty
>>
>>     fmap :: (FunctorConstraint f b) =>  (a ->  b) ->  f a ->  f b
>>
>> class Empty a
>> instance Empty a
>
>
> Do you really need this Empty class?

Depends on what you want. You do need it if you want to be able to use
'FunctorConstraint f' itself as a type of kind * -> Constraint, for
example to say type FunctorWithoutConstraint f = (Functor f,
FunctorConstraint f ~ Empty).

> That seems inconvenient. I had hoped
> you would be able to write something like
>
>
>    type FunctorConstraint f :: * ->  Constraint
>    type FunctorConstraint f a = ()
>

See this thread:
http://www.mail-archive.com/glasgow-haskell-users <at> haskell.org/msg20792.html
(Continue reading)

Permalink | Reply | 0 comments |
headers
Bas van Dijk | 1 Mar 2012 17:33
Picon
Gravatar

Re: Functor instance for Set?

On 1 March 2012 13:20, Twan van Laarhoven <twanvl <at> gmail.com> wrote:
> On 01/03/12 09:31, Bas van Dijk wrote:
>>
>> class Functor f where
>>     type FunctorConstraint f :: * ->  Constraint
>>     type FunctorConstraint f = Empty
>>
>>     fmap :: (FunctorConstraint f b) =>  (a ->  b) ->  f a ->  f b
>>
>> class Empty a
>> instance Empty a
>
>
> Do you really need this Empty class? That seems inconvenient. I had hoped
> you would be able to write something like
>
>
>    type FunctorConstraint f :: * ->  Constraint
>    type FunctorConstraint f a = ()
>
>
> Twan
>
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries

In GHC-7.4.1 that will give the following error:
(Continue reading)

Permalink | Reply | 0 comments |
headers
Twan van Laarhoven | 2 Mar 2012 19:52
Picon
Gravatar

Re: Proposal: add 'findLess' and variants to containers

On 12/02/12 14:14, Twan van Laarhoven wrote:
> Discussion deadline: 2 weeks from now; Sunday, 26 February 2012.

The deadline for discussion has passed. There were no explicit votes for 
or against, but 4 reactions that count as positive, and 1 as unconvinced.

The only issue seems to be the names:

> Thanks for the benchmark. In light of this and your other arguments I
> think we should add the functions. Lets settle on the names.

I have made a case for /lookup(Less|Greater)(Equal)?/, based on the fact 
that lookup* functions return "Maybe x" values, while find* functions 
return values without a maybe wrapper. But I don't really care that 
much. Flipping a coin between "find" and "lookup" will also work for me :)

Twan
Permalink | Reply | 8 comments |
headers
Johan Tibell | 2 Mar 2012 19:56
Picon
Gravatar

Re: Proposal: add 'findLess' and variants to containers

On Fri, Mar 2, 2012 at 10:52 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:

I have made a case for /lookup(Less|Greater)(Equal)?/, based on the fact that lookup* functions return "Maybe x" values, while find* functions return values without a maybe wrapper. But I don't really care that much. Flipping a coin between "find" and "lookup" will also work for me :)

I'd say lookup.
 

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Permalink | Reply | 0 comments |
headers
Christian Sattler | 2 Mar 2012 20:16
Picon

Proposal: more general unionWith for Data.Map - Summary

The discussion has been over for a month now, so I think it is prudent 
to summarize the contributions.

There have been many suggestions of a general merge function, but the 
only proposal that matches the expected runtime complexities of the 
specializations to union/intersection/difference/symmetricDifference 
came from Jan-Willem Maessen, who suggested a general merge function of 
the following type:

mergeWithKey :: (Ord k) => (k -> a -> b -> Maybe c) -> (Map k a -> Map k 
c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c

Existing union/intersection/difference and the missing 
symmetricDifference can be implemented as specialization of this 
function with no loss to runtime complexity when inlining is used, and 
even symmetrizing the behaviour of union.

Feedback indicated it is worth to unify the existing mess with an 
abstract foundation, with otherwise no negative reactions. As such, I 
propose to go through with this.

Christian
Permalink | Reply | 2 comments |

Gmane