Opened 3 years ago

Last modified 3 months ago

#7495 new feature request

generalizing overloaded list syntax to Sized Lists, HLists, HRecords, etc

Reported by: nwf Owned by: carter
Priority: normal Milestone: 7.12.1
Component: Compiler Version: 7.6.1
Keywords: Cc: giorgidze@…, info@…, jeroen.weijers@…, eir@…, gershomb@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking: #9883
Related Tickets: #9883 Differential Revisions:

Description

First, sorry if I've missed an earlier request for this in trac; a few searches did not turn up anything relevant.

I've recently taken to doing a lot of work with heterogenous lists (thanks to the DataKinds work) and find the forced-cons-and-nil style of writing lists (e.g. "a:+b:+c:+HN") to be sort of unpleasant.

Would it be possible to allow rebinding list-literal syntax? Off the top of my head I think something like the following might be workable, if only I could stop [] and (:) from being in scope, even with -XNoImplicitPrelude. (Example requires -XDataKinds -XFlexibleInstances -XGADTs -XMultiParamTypeClasses -XTypeOperators)

class HasNil a where
  ([])  :: a
  isNil :: a -> Bool

class HasCons e l l' | e l -> l', l' -> e l where
  (:)    :: e -> l -> l'
  uncons :: l' -> Maybe (e,l)

-- For homogeneous lists...
instance HasNil [a] where
  ([])  = ([])
  isNil = null

instance (a ~ a1, a ~ a2) => HasCons a [a1] [a2] where
  (:)           = (:)
  uncons []     = Nothing
  uncons (x:xs) = Just (x,xs)

-- For HLists...
data HList as where
  HN   :: HList '[]
  (:+) :: a -> HList as -> HList (a ': as)

instance HasNil (HList '[]) where
  ([])  = HN
  isNil = const True

instance (a ~ a1, as ~ as1) => HasCons a (HList as) (HList (a1 ': as1)) where
  (:)              = (:+)
  uncons (a :+ as) = Just (a,as)

Change History (17)

comment:1 Changed 3 years ago by simonpj

  • Cc giorgidze@… info@… jeroen.weijers@… added
  • difficulty set to Unknown

Yes, and an implementation is well advanced; see OverloadedLists. I've cc'd the George, Achim, and Wejers, who are doing it.

Simon

comment:2 Changed 3 years ago by monoidal

Should this be marked as fixed?

comment:3 Changed 3 years ago by nwf

I don't think the extant proposal at OverloadedLists addresses the heterogeneous types I was after?

comment:4 Changed 3 years ago by goldfire

  • Cc eir@… added

I agree with nwf. It seems the current implementation can't deal with heterogeneous lists. I, too, would enjoy being able to use nicer notation for my lists.

comment:5 Changed 2 years ago by igloo

  • Milestone set to 7.8.1

comment:6 Changed 16 months ago by thoughtpolice

  • Milestone changed from 7.8.3 to 7.10.1

Moving to 7.10.1

comment:7 Changed 11 months ago by carter

  • Owner set to carter
  • Summary changed from Rebindable list syntax? to generalizing overloaded list syntax to Sized Lists, HLists, HRecords, etc

I've been working on designing a set of classes that subsumes this proposal. the work in progress in the class design can be found https://github.com/cartazio/HetList/blob/master/HetList.hs

It doesn't yet have the analogues machinery to support the older fromList style instances, but thats easy to add.

As part of the dev I'm making sure I can write useful instances for the fancy HList libs that are in the while, like HList and Vinyl

after another week or two of polish, I hope to have a candidate patch with the right desugaring (plus some extra work to support current style instances if possible)

comment:8 Changed 9 months ago by carter

  • Blocking 9883 added

comment:9 Changed 8 months ago by thoughtpolice

  • Milestone changed from 7.10.1 to 7.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:10 Changed 6 months ago by gershomb

  • Cc gershomb@… added

comment:11 Changed 3 months ago by s9gf4ult

Hello. I propose little different solution. I dont think we should put methods isNil and uncons inside of this proposal, because they do not relate with lists construction. Here is full example of my proposal:

{-# LANGUAGE
  FlexibleInstances
, TypeOperators
, TypeFamilies
, DataKinds
, GADTs
  #-}

import GHC.TypeLits

-- | Types which can be constructed with 'cons' should instantiate this
class Cons a where
    type Head a :: *
    type Tail a :: *
    cons :: Head a -> Tail a -> a

-- | And types which is a empty list should instantiate this
class Nil a where
    nil :: a


---------------------------------
-- Simple homogenous lists     --
---------------------------------

instance Cons [a] where
    type Head [a] = a
    type Tail [a] = [a]
    cons elem b = elem:b

instance Nil [a] where
    nil = []

-- | synoym for '[10, 20, 42]'
justList :: [Int]
justList = cons 10 $ cons 20 $ cons 42 $ nil


-------------------------------
-- Simple heterogenous lists --
-------------------------------

-- | Simple heterogenous list
data HList (typs :: [*]) where
    HNil :: HList '[]
    HCons :: typ -> HList typs -> HList (typ ': typs)

instance Cons (HList (t ': ts)) where
    type Head (HList (t ': ts)) = t
    type Tail (HList (t ': ts)) = HList ts
    cons = HCons

instance Nil (HList '[]) where
   nil = HNil

-- | synonym of '[10, 20, "hello"]'
hlist :: HList '[Int, Integer, String]
hlist = cons 10 $ cons 20 $ cons "hello" nil


---------------------------------------------------------------------------
-- More complex heterogenous list with constraints for it's elements     --
---------------------------------------------------------------------------

-- | Checks that element contained in type list
type family Elem (typ :: *) (typs :: [*]) :: Bool where
    Elem typ '[]             = 'False
    Elem typ (typ ': typs)   = 'True
    Elem typ1 (typ2 ': typs) = Elem typ1 typs

-- | Heterogenous list with uniq elements
data UniqHList (typs :: [*]) where
    UHNil  :: UniqHList '[]
    UHCons :: ('False ~ (Elem typ typs))
           => typ -> UniqHList typs -> UniqHList (typ ': typs)

-- | Look at instance constraint, it is the same constraint as in
-- 'UHCons' constructor
instance ('False ~ (Elem t ts)) => Cons (UniqHList (t ': ts)) where
    type Head (UniqHList (t ': ts)) = t
    type Tail (UniqHList (t ': ts)) = UniqHList ts
    cons = UHCons

instance Nil (UniqHList '[]) where
    nil = UHNil


-- | This should be written as '[10, "string", 42.2, 20]'
uniqHlist :: UniqHList '[Integer, String, Double, Int]
uniqHlist = cons 10 $ cons "string" $ cons 42.2 $ cons 20 nil

---------------------------------------
-- Vectors parametrized with length  --
---------------------------------------

data Vector (len :: Nat) a where
    VNil :: Vector 0 a
    VCons :: a -> Vector len a -> Vector (len + 1) a

-- | Look at the constraint again. It is a little hackish because GHC
-- can not infer that __len ~ ((len - 1) + 1)__
instance (len ~ ((len - 1) + 1)) => Cons (Vector len a) where
    type Head (Vector len a) = a
    type Tail (Vector len a) = Vector (len - 1) a
    cons = VCons

instance Nil (Vector 0 a) where
    nil = VNil

vector :: Vector 3 Int
vector = cons 1 $ cons 2 $ cons 3 $ nil

It is compilable and contains instances for some complex cases. The method cons shoud be considered as (:) and nil should become [].

What do you think? Cheers!

comment:12 Changed 3 months ago by carter

hrm, thats an intersting take

the analogous design I was playing with was

class HetCons (f:: k -> * ) (f':: m -> * ) (h :: * ) (tl:: k) (res :: m)
          | f-> f', f'-> f
            ,f h tl -> res , f h res -> tl, f res tl -> h
            , f' res -> h
            , f  tl res  -> h
            , f'  tl res -> h

                 where
  hcons :: h  -> f tl -> f' res


class HetNil nil where  -- (f:: k -> * ) (a :: k)  where
  hnil :: nil


i have a few example instances in https://github.com/cartazio/HetList/blob/master/HetList.hs, and type inference would work out pretty nicely.

one idea that i dont think we've articulated or explored properly is understanding how to use pattern synonym machinery to overload pattern matching list syntax or something!

comment:13 Changed 3 months ago by s9gf4ult

Your example is much more complex, why so many parameters in HetCons and functional dependencies?

Pattern matching overload is interesting idea. Pattern (x:xs) should be considered by compiler as HCons x xs for HList, but compiler knowns about HList just after type inference and see pattern (x:xs) after parsing and desugaring, so pattern (x:xs) must be replaced with HCons x xs after type inference somehow. I am not very familiar with GHC internals anyway.

comment:14 Changed 3 months ago by simonpj

I like comment:11.

Do start a wiki page to describe the design. Issues you don't cover yet

  • Pattern matching
  • What about [a,b..c] and friends?
  • One could add this as a different and incompatible extension to the existing OverloadedLists, but it would be better to get the best of both worlds. Can we? What can the existing OverloadedLists do that the new design cannot?

There are probably more issues. A wiki page is a good place to put the current best-effort design; while the ticket is a good place to discuss it.

Simon

comment:15 Changed 3 months ago by s9gf4ult

  • Pattern matching: I believe we should not put pattern matching into OverloadedLists and stay with just list construction. It looks like implementation of generic list construction is simpler than generic pattern matching. The usability of list construction is higher because things like
[ OneTypeConstructor  
, OtherTypeConstructor
, "string"
]

looks more clean and simple to write than

HCons OneTypeConstructor   $ 
HCons OtherTypeConstructor $ 
HCons "string" HNil 

but when you pattern match some list you probably expect some concrete list type, not just some list (heterogeneous or homogeneous) with some elements.

Maybe add separate OverloadedListPatterns extension instead?

  • About [a,b..c]: There should nothing changed for homogeneous lists, but heterogeneous lists can not be constructed dynamically, especially lists like [1..]. Maybe it would be nice to make sugar [a,b..f] unwrap to
HCons a $ 
HCons b $ 
HCons c $ 
HCons e $ 
HCons f HNil 

but it is not an option for homogeneous lists, especially lists like [1,2..10000000].

Maybe special syntax like [1,2...5] (three dots) for constructing heterogeneous lists at compile time?

  • I don't see any things which current OverloadedLists can do and this new can not. Maybe some issues with type inference ...

comment:16 Changed 3 months ago by simonpj

I don't see any things which current OverloadedLists can do and this new can not.

Well, how about pattern matching and [1..n]?! Maybe people are using those already. Have you talked to the authors of OverloadedLists to see what they think? Do you expect this new design to replace OverloadedLists, or just be a competing extension?

Let me continue to encourage you to start a wiki page explaining the design and its relationship to other extensions. Build up a community of people who support the idea, and work with them to refine it. Ultimately, develop a patch.

Good work!

Simon

comment:17 Changed 3 months ago by s9gf4ult

You absolutely right about pattern matching (using view patterns) and [1..n] expressions. I just missed this features of OverloadedLists. It is not obvious how to deal with it.

My code differs from original code of this proposal, I am also not an author of proposal. Maybe @carter should start wiki page?

Note: See TracTickets for help on using tickets.