June 2019 - Libraries

Re: Data.Graph transitive closure
by Alan Isaac 21 Jun '19

21 Jun '19

Feedback from an occasional Haskell user: I would use it. I've noticed that computational implementations of "transitive closure" often deviate from my (user-level) understanding of the standard mathematical definition. Specifically, self loops are often discarded. I assume/hope the math def will be used in haskell. A prominent example is Mathematica's TransitiveClosureGraph command. E.g., `TransitiveClosureGraph[{a -> b, b -> c, c -> a}]` has no self loops, even though `a` is clearly reachable from `a`, and TransitiveClosureGraph[{a -> a, b -> b, c -> c}]` is empty!) In the past networkx also had this flaw (although they indicated a plan to fix this; I'd have to recheck the current status). Cheers, Alan Isaac PS My apologies if I misread your post; I understood it to request user feedback, not just developer assessment. On 6/20/2019 8:00 AM, David wrote: > I just noticed that Data.Graph doesn't offer a transitive closure > operation. Looking into implementing one, I discovered that doing so > efficiently has been the subject of non-trivial research [*]. So if there's > any demand, we should try to implement a reasonably efficient version in > containers. Anybody want one?

1 0

Data.Graph transitive closure
by David Feuer 20 Jun '19

20 Jun '19

I just noticed that Data.Graph doesn't offer a transitive closure operation. Looking into implementing one, I discovered that doing so efficiently has been the subject of non-trivial research [*]. So if there's any demand, we should try to implement a reasonably efficient version in containers. Anybody want one? [*] http://www.cs.hut.fi/~enu/thesis.html

4 3

Add instance Bounded (Ratio a)
by Dannyu NDos 16 Jun '19

16 Jun '19

instance (Integral a, Bounded a) => Bounded (Ratio a) where minBound = minBound % 1 maxBound = maxBound % 1

4 4

Laws for Show and Read?
by Dannyu NDos 16 Jun '19

16 Jun '19

Shouldn't it be laws that "show" must be injective and "read" must be surjective? Without such laws, one could define: data Foo = Foo instance Show Foo where show _ _ = id instance Read Foo where readPrec = pfail which should be prevented.

8 10

Strictness in Kinds
by Andrew Martin 14 Jun '19

14 Jun '19

TLDR: I wrote up an idea: https://gist.github.com/andrewthad/90a4b23051870d14afb4ba064699bc5b. Last night, the phrase "strictness in kinds" just stuck in my head. I could have sworn I'd heard it or read it before. But after some googling, I couldn't find anything on it. So, I started think about what it would look like for GHC to track strictness in the kind of an expression. It's kind of like proposals B2 and B3 from https://gitlab.haskell.org/ghc/ghc/wikis/unlifted-data-types, but I thought I'd share it here. -- -Andrew Thaddeus Martin

1 0

Proposal: Expose reverse topological ordering in Data.Graph
by James Parker 06 Jun '19

06 Jun '19

Hi, I’d like to expose reverse topological ordering in Data.Graph. I’ve created a pull request <https://github.com/haskell/containers/pull/638> that implements this. I named it `revTopSort` for now, but am fine with alternatives. Thanks, James Parker

2 2

add instance Monad (Arg a)
by Dannyu NDos 03 Jun '19

03 Jun '19

I think it's reasonable to make Arg as a writer monad with alternate ordering.

1 0

Memory Barriers with STM and MVar
by Andrew Martin 03 Jun '19

03 Jun '19

I've been poking around in old threads and in the GHC source, and I cannot find this documented anywhere. What are the guarantees that GHC provides around load/store reordering when it comes to using MVar or TVar+retry+atomically. For example: import Data.Primitive import Control.Concurrent.MVar ... foo :: IO () foo = do ... writeByteArray myArr 13 (42 :: Word) putMVar myMVar () If there is another thread that calls takeMVar followed by `readByteArray myArr 13`, is it guaranteed by GHC to see the 42 that's been written to the array. Same question applies for situations using STM facilities to accomplish blocking behavior that MVar gives us. Any documentation or pointers to places in GHC source where these barriers are guaranteed would be appreciated. -- -Andrew Thaddeus Martin

3 8