September 2011 - Haskell-prime

Re: TypeFamilies vs. FunctionalDependencies & type-level recursion
by Anthony Clayden 11 Jun '12

11 Jun '12

> > Sorry for the late reply. Thanks Oleg, I take it the Northern hemisphere is now on academic summer holidays. > > [snip] > > > Finally, I still think most of the "magic" in everything > > we've been talking about boils down to being able to > > have a type variable that can take on any type *except* > > a certain handful. This would allow us to avoid > > overlapping instances of both classes and type families, > would allow us to define TypeEq, etc. Moreover, it would > > be a more direct expression of what programmers intend, > > and so make code easier to read. Such a constraint > cannot be part of the context, because > > Alas, such `type variables' with inequality constraints > are quite complex, and the consequences of their > introduction are murky. Let me illustrate. First of all, > the constraint /~ (to be used as t1 /~ Int) doesn't help > to define TypeEq, etc. because constraints are not used > when selecting an instance. ... Yes indeed we can't use constraints when selecting an instance, several posters have pointed this out. I've suggested we call these inequality 'restraints' rather than 'constraints'. And a different syntax has been proposed, similar to pattern guards: type instance TypeEq a b | a /~ b = HTrue > Instances are selected only by > matching a type to the instance head. Instance selection > based on constraints is quite a change in the type checker > , and is unlikely to be implemented. I agree that selecting instances based on constraints would be abig change, but ... Selecting instances based on inequalities is already implemented in GHC and Hugs. (And has been successfully used for over a decade.) You've used it extensively yourself in the HList work, and much other type-level manipulation (such as IsFunction). Unfortunately, it's not called 'instance selection based on inequalities' (or some such), and its implementation got all mixed up with Functional Dependencies, which to my mind is an orthogonal part of the design. Instance selection based on inequalities is called 'Overlapping Instances'. The difficulty in adopting it into Haskell prime is that it isn't thoroughly specified, and you can currently only use it with FunDeps. To avoid confusion with FunDeps, let's imagine we could use overlapping instances with Type Families: type family HMember e l type instance HMember a HNil = HFalse type instance HMember a (HCons a l') = HTrue type instance HMember a (HCons b l') = HMember a l' Selecting that last instance implies a /~ b. (Otherwise the HTrue instance would be selected). Using inequality restraints, we'd write that last instance as: type instance HMember a (HCons b l') | a /~ b = HMember a l' And by putting an explicit inequality we are in fact avoiding the trouble with overlaps and all their implicit logic: The compiler can check that although the instance heads do overlap, the inequality disambiguates the instances. So type inference could only select one instance at most. I think this could be implemented under the new OutsideIn(X) type inference: Inference for the ordinary instances proceeds as usual. Inequalities give rise to implication terms(as used for GADTs), with the inequality in the antecedent: (a /~ b) implies (TypeEq a b ~ HFalse) As with GADTs, inference needs evidence that a /~ b before applying the consequent. There is no danger of clashing with other instances of TypeEq, because the instance (including inequality) doesn't overlap any of them. (I made some long posts to the Haskell-prime list last month, explaining in more detail, and responding to your TTypeable suggestion.) > > _______________________________________________ > Haskell-prime mailing list > Haskell-prime(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-prime

7 22

left and right sections extended
by Christian Maeder 01 Oct '11

01 Oct '11

Hi, the following sections are currently legal in Haskell: (a + b +) and (++ a ++ b) because + is left and ++ is right associative. I would like to write (+ 1 +) and (++ " " ++) as legal generalized sections, too, to stay for (\ a -> (a + 1 +)) and (\ a b -> a ++ " " ++ b) respectively. The right-associative case would be "flip (\ b -> (++ " " ++ b))" Such an extension would be easy to implement and it would also be a generalization of putting parenthesis around symbols as in (+) or (++). Extending the grammar is easy: aexp -> ... | ( infixexp qop ) (left section) | ( qop⟨-⟩ infixexp ) (right section) Some thoughts are needed to exclude the illegal cases (as done for left and right sections). Is this worth a formal proposal or is this too confusing? Cheers Christian

2 1

Please apply the comparison function given to nubBy to elements of the list in the order in which they occur in the list.
by Cale Gibbard 28 Sep '11

28 Sep '11

I just tried this in ghci-7.0.3: ghci> nubBy (>=) [1,2,3,4] [1] Think about what this is doing: it is excluding 2 from the list because 2 >= 1, rather than including it because 1 >= 2 fails. I think an important convention when it comes to higher order functions on lists is that to the extent which is possible, the function parameters take elements from the list (or things computed from those) in the order in which they occur in the original list. If we reimplement it in the obvious way: ghci> let nubBy f [] = []; nubBy f (x:xs) = x : filter (not . f x) (nubBy f xs) ghci> nubBy (>=) [1,2,3,4] [1,2,3,4] I'm aware that the Report (strangely!) explicitly leaves the behaviour of nubBy unspecified for functions which are not equivalence relations, but the behaviour given by the Report implementation (the opposite of the current behaviour in GHC) is useful and desirable nonetheless. I'm sure I've written about this before. I'm not entirely sure what happened to the previous thread of discussion about this, but it just came up again for me, and I decided that I was sufficiently irritated by it to post again. Another thing perhaps worth pointing out is that the parameters to mapAccumR have always been backwards (compare it with foldr). Few enough people use this function that I'm fairly sure we could just change it without harm. - Cale

5 8

Re: Please apply the comparison function given to nubBy to elements of the list in the order in which they occur in the list.
by Christian Maeder 21 Sep '11

21 Sep '11

Am 20.09.2011 20:21, schrieb Edward Kmett: [...] > I would suggest you rephrase this as a formal proposal, then I can > happily vote +1. Seeing the "wonderful" interrelation between elem, nub, nubBy and i.e. unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs intersectBy eq xs ys = [x | x <- xs, any (eq x) ys] (note that "any (eq x)" could be "elemBy eq") I see hardly a chance to make a sensible proposal. I think, it is wrong to change the implementation of "elem" and "notElem" since I expect the "key" to be the first argument of the eq-comparison (in contrast to the REPORT_PRELUDE!). But this all would not matter if the eq-function are always symmetric, which may be not the case in practise. So a change could break existing code. > I'd also suggest rephrasing rhe mapAccumR as a formal proposal. I'm not > sure yet of whether or not I'd be behind that one, but make both > proposals separately, so they can pass individually. I also don't see a relation to mapAccumR, so why don't you make such a separate proposal? C.

1 0