- Libraries - Haskell.org

[Proposal] Add instance Monoid a => Monoid (Const a b)
by haskell＠nand.wakku.to 13 Oct '13

13 Oct '13

Hello, I think this a Monoid instance on Const would be useful. The motivation comes from ‘lens’, where folds come out as (a -> Const a a) -> s -> Const a s. This instance, together with the Monoid a => Monoid (r -> a) instance, allows folds themselves to be an instance of Monoid, allowing for some really pretty code. Example of the instance body: > instance Monoid a => Monoid (Const a b) where > mempty = Const mempty > mappend (Const a) (Const b) = Const (mappend a b) Examples of it being used together with lens: >>> "Hello, world!" ^.. mconcat [ix 2, ix 7, ix 1] "lwe" Discussion Period: 2 weeks

12 16

Re: [Proposal] Renaming (:=:) to (==)
by Edward Kmett 12 Oct '13

12 Oct '13

On Sat, Oct 12, 2013 at 1:29 AM, Iavor Diatchki <iavor.diatchki(a)gmail.com>wrote: > Hello, > > I am not sure what version of GHC.TypeLits you looked at, but as of the > other day the code in there is almost the same as what you propose (except > for the use of different classes). > My copy of the code was a couple of days out of date, from when I started the patch. On Fri, Oct 11, 2013 at 12:54 PM, Edward Kmett <ekmett(a)gmail.com> wrote: > >> >> They are currently impossible to implement without using very deep >> voodoo. See the magicSingIId note. >> >> > The `magicSingI` has been redone and is quite a bit simpler now. Note > [magicDictId magic] describes the current approach. Still, if we can think > of a way to get rid of it, I'm strongly in support. > > >> If we bring in GHC.Reflection. (I've almost finished a patch for it, my >> only remaining hangups are in the wiredIn itself) then the code in >> GHC.TypeLits for KnownNat and KnownSymbol can go away, and those two >> definitions can use reflection internally. >> >> > `KnowNat` and `KnownSymbol` are the basic classes that provide the > built-in instances for type-level literals (SingI is gone). I don't see > any way around having some built-in code like that. > Indeend, `natVal` is implemented almost exactly like this. It'd be trivial > to provide an instance for the `Reify` class if we needed to: > > instance KnowNat n => Reifying (n :: Nat) where type Reified n = > Integer; reflect# = natVal > > If those are the classes being generated now, then I can use that to generate the instances for Reifying at those kinds. > > Those classes can melt away and disappear >> >> > Do you mean by providing built-in instances for `Reify` instead? If so, > this is mostly a renaming, and I am not so keen on making the change as I > like the simplicity of `KnownSym` and `KnownNat`. Also---and this is an > implementation detail---their dictionaries are simpler than the one for > `Reify`: they just carry around the actual value, integer or string, while > the dictionaries for `Reify` have to store a whole function. I think this > matters when you package them in existentials, no? > The instance for Reifying holds a function from Proxy# a which is of unlifted kind and has no representation. Behind the scenes they should look substantially identical. Using something like the Tagged newtype could make them definitely identical behind the scenes. I'm okay with leaving them as it is. I mostly was noting that if we did consolidate then we'd get a slight code reduction. > and internally the implementation of someNatVal, and someSymbolValbecome much less horrific: >> >> -- | This type represents unknown type-level natural numbers. >> data SomeNat = forall (n :: Nat). Reifying n => SomeNat (Proxy# n) >> >> -- | Convert an integer into an unknown type-level natural. >> someNatVal :: Integer -> Maybe SomeNat >> someNatVal n >> | n >= 0 = Just (reify# n SomeNat) >> | otherwise = Nothing >> >> > Well, the current implementation is almost exactly this! I don't really > know how `reify#` is supposed to work, but it certainly seems to do > something very similar to what `magicDict` does, so we should probably make > sure that there is only one implementation. I would guess that you can use > `magicDict` to implement `reify#`. The other way around would also be OK > with me as long as I don't have to use the `Reify` class, and can use > directly the simpler (no type functions, no kind polymorphism) > `KnownSymbol` and `KnownNat` classes. > In core, stripping away the newtypes and coercions reify# winds up looking like reify a k = k (\_ -> a) proxy# The lambda there is ignoring a Proxy#, which is an unlifted argument without representation, and the proxy# argument at the end is similar. Also, doesn't `reify#` introduce a coherence issue? `someNatVal` and the > instances for `KnownNat` are carefully engineered to provide a consistent > view to the programmer, but as far as understand, this is not the case with > `Reifying`. For example, consider the following code: > data {- kind -} K > > instance Reifying (a :: K) where > type Reified a = Integer > reflect# _ = 5 > > getK :: Reifying a => Proxy (a :: K) -> Integer > getK = reflect# > > test :: Integer > test = reify# 6 getK > > It is not at all obvious if `test` should evaluate 5 (using the global > instance) or 6 (using the locally supplied evidence), and the choice seems > highly dependent on the mood of the constraint solver. > Fair point. I was attempting to generalize reify# to allow it to instantiate at kinds other than *, to enable it to subsume your existing usecase. When restricted to * there isn't a coherence issue, as there is no such overarching instance, but also simply by providing any concrete instance of Reifying under kind * means that any attempt by the user to define such an instance Reifying (a :: *) would overlap, preventing this conflict. I'll go back to the simpler version of reify#, which doesn't attempt to let you reify at other kinds, and leave TypeLits alone. This simplifies my task considerably. -Edward

1 0

Re: Flipped function application
by John Wiegley 12 Oct '13

12 Oct '13

>>>>> Andreas Abel <andreas.abel(a)ifi.lmu.de> writes: > Here is a comprehensive list of existent (H) and envisioned (W,M) > application and composition operators. Great summary, Andreas, thank you. -- John Wiegley FP Complete Haskell tools, training and consulting http://fpcomplete.com johnw on #haskell/irc.freenode.net

1 0

[Proposal] Renaming (:=:) to (==)
by Edward Kmett 11 Oct '13

11 Oct '13

As part of the discussion about Typeable, GHC 7.8 is going to include a Data.Type.Equality module that provides a polykinded type equality data type. I'd like to propose that we rename this type to (==) rather than the (:=:) it was developed under. We are already using (+), (-), (*), etc. at the type level in type-nats, so it would seem to fit the surrounding convention. I've done the work of preparing a patch, visible here: https://github.com/ekmett/packages-base/commit/fb47f8368ad3d40fdd79bdeec334… Thoughts? Normally, I'd let this run the usual 2 week course, but we're getting down to the wire for 7.8's release. Once 7.8 ships, we'd basically be stuck with the current name forever. Discussion Period: 1 week -Edward Kmett

14 27

Flipped function application
by Wvv 11 Oct '13

11 Oct '13

It's looking very strange, that such easy function as flipped function application is still absent at the base. x # f = f x infixl 1 # -- infix (#) must conflict neither ($), nor (.) We could add it to Data.Functions and probably to Prelude. It is very useful function to get rid of parentheses (1); "object looking" record style (2); left-to-right function reading style (3); nice looking last argument-data (4) 1) xs # map $ someLong function x # some . function . composition 2) car # color 3) myString # lines # map words # concat # filter myFilter # unwords 4) eitherData # either (left long function) (right long function) Many of possible names are already busy. I made the review of possible names: # - free; disadvantage: possible conflicts with Magic Hash ## - free; disadvantage: heavy looking; possible conflicts with Magic Hash `to` - free; disadvantage: not easy to read composite functions <: - free; & - free; (conflict with fgl package) disadvantage: looking like boolean operator .: - free; .:. - free; disadvantage: many dots <-| - free; disadvantage: long name <+ - free; <~ - free; :~ - free; -|- - free; disadvantage: bad looking; % - busy: Data.Ratio %% - free; disadvantage: heavy looking; ^ - busy: Prelude .^. - free; ^^^ - free; disadvantage: long name |.| - free; disadvantage: strange looking; *$ - free; disadvantage: looking like ($) <| - busy: Data.Sequence < - busy: Prelude << - busy: Text.Html; Text.XHtml.* from html and xhtml package <<< - busy: Control.Category * - busy: Prelude ** - busy: Prelude *** - busy: Control.Arrow <*> - busy: Control.Applicative <**> - busy: Control.Applicative !! - busy: Prelude -| - busy: Control.Parallel.Strategies your suggestion - free; I prefer (#) , then (.:) and then (<:). What do you prefer? Possible looking (copy to your editor to taste them): 2.1 # max 50 # cos # tan # negate # ceiling 2.1 ## max 50 ## cos ## tan ## negate ## ceiling 2.1 `to` max 50 `to` cos `to` tan `to` negate `to` ceiling 2.1 <: max 50 <: cos <: tan <: negate <: ceiling 2.1 & max 50 & cos & tan & negate & ceiling 2.1 .: max 50 .: cos .: tan .: negate .: ceiling 2.1 .:. max 50 .:. cos .:. tan .: negate .:. ceiling 2.1 <-| max 50 <-| cos <-| tan <-| negate <-| ceiling 2.1 <+ max 50 <+ cos <+ tan <+ negate <+ ceiling 2.1 <~ max 50 <~ cos <~ tan <~ negate <~ ceiling 2.1 % max 50 % cos % tan % negate % ceiling 2.1 %% max 50 %% cos %% tan %% negate %% ceiling 2.1 .^. max 50 .^. cos .^. tan .^. negate .^. ceiling 2.1 :~ max 50 :~ cos :~ tan :~ negate :~ ceiling 2.1 |.| max 50 |.| cos |.| tan |.| negate |.| ceiling 2.1 -|- max 50 -|- cos -|- tan -|- negate -|- ceiling -- View this message in context: http://haskell.1045720.n5.nabble.com/Flipped-function-application-tp5738131… Sent from the Haskell - Libraries mailing list archive at Nabble.com.

27 45

Data.Type.Equality and coercions
by Richard Eisenberg 10 Oct '13

10 Oct '13

I've noticed two infelicities with the Data.Type.Equality module that I added this summer (according to this proposal: http://ghc.haskell.org/trac/ghc/wiki/TypeLevelReasoning) For those of you unfamiliar, the key definition is this: > data a :=: b where > Refl :: a :=: a This is essentially just like (~), but in * instead of Constraint. 1. There is a function > coerce :: (a :=: b) -> a -> b This function conflicts with the new function of the same name in the Coercible class (defined in GHC.Prim), with the type > coerce :: Coercible a b => a -> b So, these functions are very similar. The first uses explicit nominal equality, while the second uses implicit representational equality. Neither quite subsumes the other. (Disclaimer: I may or may not have named both of these myself, albeit separated by several months. If I did, sorry for creating this problem.) My slight inclination: rename the Coercible version to `coerceRep`, as it really is doing a runtime coercion, as opposed to `coerce`. But, I'm quite happy for someone else to have a better idea. 2. There is a useful function that should be added to Data.Type.Equality: > gcoerce :: (a :=: b) -> ((a ~ b) => r) -> r > gcoerce Refl x = x For an example of this in action, see https://gist.github.com/goldfirere/6902431, which is related to #8423 but can be read standalone. I don't think that gcoerce can subsume coerce because they have different type inference implications. In particular, the types of the coercion in `coerce` can improve the type of the equality witness, whereas this is not possible in `gcoerce`. Discussion time: 1 week. Thanks! Richard

6 6

Re: I've forked test-framework
by Greg Weber 09 Oct '13

09 Oct '13

I would like to reduce the amount of test framework fragmentation. A better path forward might be to use the newer more extensible and well maintained tasty package. I am imagining it is trivial to create a compatibility layer with the previous test-framework or to find and replace, but that might not be the case.

6 8

TypeLits
by Richard Eisenberg 08 Oct '13

08 Oct '13

Hi Iavor, It was very nice to see you last week -- it's too bad we have to wait another year for another ICFP! :) A question I got asked between sessions at ICFP led me to look at singletons again, and it seems that singletons has gone out of sync with TypeLits. When I looked closely at TypeLits, I saw a number of changes there, and I wonder if we can think a bit about the design before 7.8 rolls out. Forgive me if some of these suggestions are not new -- I just haven't looked closely at TypeLits for some time. Specifically: - I see that you define singleton instances for Bool. This makes sense, if we are to avoid orphan instances of the various singletons classes. But, it would seem helpful to define singleton support for more than just Bool here, if we are going down this road. For example, singletons for [], Maybe, Either, and the tuples are quite useful. - You don't export the constructors for Sing (k :: Bool). I think these need to be publicly visible. - I believe that Edward's reflection package will be incorporated into base. (Edward?) If so, it's possible that incoherentForgetSing can be cleaned up somewhat. - Why use LocalProxy? What's wrong with plain old Proxy? - I see Show and Read instances defined for singletons. Though these are useful, they prevent clients from defining their own instances, and I can imagine a user (possibly me) wanting a singleton to have a distinct Show instance from its base type. Perhaps these should be moved to a different module which can selectively be imported? - The definition for (:~:) is redundant with the new Data.Type.Equality. - The eqSing... functions are now redundant with the EqualityT class in Data.Type.Equality. Instead, TypeLits should probably define instances for EqualityT. - TypeLits defines KindIs, which is redundant with Data.Proxy's KProxy. It might be that KindIs is easier to use than KProxy, but base probably shouldn't have both types floating around. - I'm confused about IsZero. How is it different (in practical usage situations) from eqSingNat? Also, I'd like to note that IsZero uses a unary representation, which might be problematic. - The definitions for Nat1 don't need to be in base. Perhaps we want them there -- I think it will get a lot of use -- but maybe we should just think about it for a moment before going forward. I should admit that the redundancies are new -- after some discussion in the spring, I finally implemented the new bits that are now redundant with TypeLits only a month or two ago. --- Now having posed these questions, here are my proposed answers: - To avoid orphans, TypeLits should define singleton instances for all the types above, with all constructors exported. - Remove redundancy with other parts of base. I personally prefer KProxy over KindIs, because I find the KindIs name confusing. - Remove Show instances for singletons from base. If someone thinks these will have wide use, they can be defined in a library. - Keep Nat1 right where it is. Thoughts, anyone? Thanks, Richard

5 10

I've forked test-framework
by Bryan O'Sullivan 08 Oct '13

08 Oct '13

It doesn't build with GHC 7.8, and Max hasn't responded to pull requests or repeated comments from multiple people over a span of several weeks. https://github.com/haskell/test-framework

1 0

Proposal: Partitionable goes somewhere + containers instances
by Ryan Newton 07 Oct '13

07 Oct '13

<subject change> On Sun, Sep 29, 2013 at 3:31 AM, Mike Izbicki <mike(a)izbicki.me> wrote: > I've got a Partitionable class that I've been using for this purpose: > > https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/Cons… > Mike -- Neat, that's a cool library! Edward -- ideally, where in the standard libraries should the Partitionable comonoid go? Btw, I'm not sure what the ideal return type for comappend is, given that it needs to be able to "bottom out". Mike, our partition function's list return type seems more reasonable. Or maybe something simple would be this: *class Partitionable t where* * partition :: t -> Maybe (t,t)* That is, at some point its not worth splitting and returns Nothing, and you'd better be able to deal with the 't' directly. So what I really want is for the *containers package to please get some kind of Partitionable instances! * Johan & others, I would be happy to provide a patch if the class can be agreed on. This is important because currently the balanced tree structure of Data.Set/Map is an *amazing and beneficial property* that is *not* exposed at all through the API. For example, it would be great to have a parallel traverse_ for Maps and Sets in the Par monad. The particular impetus is that our new and enhanced Par monad makes extensive use of Maps and Sets, both the pure, balanced ones, and lockfree/inplace ones based on concurrent skip lists: http://www.cs.indiana.edu/~rrnewton/haddock/lvish/ Alternatively, it would be ok if there were a "Data.Map.Internal" module that exposed the Bin/Tip, but I assume people would rather have a clean Partitionable instance... Best, -Ryan On Sun, Sep 29, 2013 at 3:31 AM, Mike Izbicki <mike(a)izbicki.me> wrote: > I've got a Partitionable class that I've been using for this purpose: > > > https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/Cons… > > The function called "parallel" in the HLearn library will automatically > parallelize any homomorphism from a Partionable to a Monoid. I > specifically use that to parallelize machine learning algorithms. > > I have two thoughts for better abstractions: > > 1) This Partitionable class is essentially a comonoid. By reversing the > arrows of mappend, we get: > > comappend :: a -> (a,a) > > By itself, this works well if the number of processors you have is a power > of two, but it needs some more fanciness to get things balanced properly > for other numbers of processors. I bet there's another algebraic structure > that would capture these other cases, but I'm not sure what it is. > > 2) I'm working with parallelizing tree structures right now (kd-trees, > cover trees, oct-trees, etc.). The real problem is not splitting the > number of data points equally (this is easy), but splitting the amount of > work equally. Some points take longer to process than others, and this > cannot be determined in advance. Therefore, an equal split of the data > points can result in one processor getting 25% of the work load, and the > second processor getting 75%. Some sort of lazy Partitionable class that > was aware of processor loads and didn't split data points until they were > needed would be ideal for this scenario. > > On Sat, Sep 28, 2013 at 6:46 PM, adam vogt <vogt.adam(a)gmail.com> wrote: > >> On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton <rrnewton(a)gmail.com> wrote: >> > Hi all, >> > >> > We all know and love Data.Foldable and are familiar with left folds and >> > right folds. But what you want in a parallel program is a balanced fold >> > over a tree. Fortunately, many of our datatypes (Sets, Maps) actually >> ARE >> > balanced trees. Hmm, but how do we expose that? >> >> Hi Ryan, >> >> At least for Data.Map, the Foldable instance seems to have a >> reasonably balanced fold called fold (or foldMap): >> >> > fold t = go t >> > where go (Bin _ _ v l r) = go l `mappend` (v `mappend` go r) >> >> This doesn't seem to be guaranteed though. For example ghc's derived >> instance writes the foldr only, so fold would be right-associated for >> a: >> >> > data T a = B (T a) (T a) | L a deriving (Foldable) >> >> Regards, >> Adam >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > >

8 17