Type-directed matching for x::xs and related list syntax

[baronfel]

I propose we change the behavior of the :: syntax as it relates to pattern matching when used with a non-list type. This in my mind is the logical sibling of #1086, mirroring those goals at the destruction-side of things rather than the construction-side.

let someArray: int [] = [ 1..10 ] // with #1086
let rec iterate (arr: int []) = 
  match arr with
  | x::xs -> // logically `xs` refers to the slice of `arr` from the second item onwards.
             // can this be done in an efficient representation with some kind of pointer tracking/sharing?
    printfn "%d" x
    iterate xs
  | [] ->
    ()

The existing way of approaching this problem in F# is to use other type-specific syntax for matching, like [| x |] for a single element array, but this has a few problems:

• another bit of syntax to remember
• arrays don't have a 'rest' syntax like lists do naturally (see xs in the first match case above)
• no other collection has the ability to even do partial matching like this, so a user must resort to writing their own active patterns in an ad-hoc fashion or manually iterating and comparing the elements they'd like to match on

Pros and Cons

The advantages of making this adjustment to F# are

• uniformity in collection matching
• adding the ability to match on collections/shapes that are not currently able to be matched on without adapters
• symmetry with #1086

The disadvantages of making this adjustment to F# are

• complexity of implementation
  • efficient traversal/caching of seq nodes so that the sequence isn't multiply-iterated in the general case
  • potentially multiple implementations necessary with a strategy pattern for deciding which helper should be used/generated at compile time
• unclear semantics of the rest pattern for non-list types
  • in the example above, is xs an array? if so, how does each iteration create an entirely new array? this would be bad for allocation IMO.
  • if a slice/span style tracker is used, this is not logically the same type as the parent collection, and so the rest pattern's output couldn't be passed in to the recursive function itself
• makes types less clear to a user without annotations
  • right now, :: means list and only list. after this change additional context would be required for a reader.

Extra information

Estimated cost (XS, S, M, L, XL, XXL): M

Related suggestions: (put links to related suggestions here): #1086

Affidavit (please submit!)

Please tick this by placing a cross in the box:

• [x] This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
• [x] I have searched both open and closed suggestions on this site and believe this is not a duplicate
• [x] This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

• [ ] This is not a breaking change to the F# language design
• [ ] I or my company would be willing to help implement and/or test this

For Readers

If you would like to see this issue implemented, please click the :+1: emoji on this issue. These counts are used to generally order the suggestions by engagement.

[jwosty]

It would be great if this worked on Span\ or Memory\.

[baronfel]

I think we'd have to flesh out support in the RFC/Implementation, but it seems reasonable to allow something like this on anything that supports an integral indexer, which I think includes Span/Memory. Definitely something to dig into though.

[jwosty]

Right, and I would consider that a vital inclusion in this feature, as it would allow you to avoid the overhead of allocating a new array everytime you use it. Suddenly, it makes traversing through arrays in this way a zero-cost abstraction.

[dsyme]

I'm actually almost more inclined to deprecate x::xs in favour of Cons(x,xs) (I'm not seriously advocating doing this, but it sometimes occurs to me of resolving the "privileged" way this operator works only for lists)

It seems to me there are very few types that support copy-free functional one-element construction and decomposition. Which is what the syntax x::xs implies in expression and pattern positions.

Things like Span and Memory use indexing, we don't really want to be making new Spans and Memory all the time do we?

[baronfel]

I'd be in support of something like Cons as shown here too, I just want a unified and efficient way to abstract across collections/containers. I went with x::xs and the related lists syntaxes at first because they are the friendliest/nicest to use.

[dsyme]

Hmmm If we went for Cons(x,xs) it would still be only for F# lists. (One problem with that is that matching constructor is called []/Nil and we don't want two names for nil. )

In your example at the top what is xs - also an array? Arrays don't work like that - you need to copy. Span can work like that but it's still often incrementally accessed via indexing.

I think what you're wanting (list-style functional decomposition of other collections) just isn't really possible (or where it is it's not really optimal). Lists are a particularly strange thing in this regard and it's why they've always been so popular since Lisp.

[roboz0r]

I could imagine a list-style decomposition for an array where the "tail" xs returns a new object that just stores the offset to the underlying array. I don't think this would be a particularly natural way to work with arrays (if I'm digging for arrays I'd want all the performance I could get and this abstraction would necessarily degrade that) usually with arrays I'm happy with the standard library or use for loops and mutation. If this were to be created I would want a different operator to :: as list decomposition has well defined behaviour and this construct would be doing a whole lot more and not in a way that benefits performance the way type-directed collection construction would work.

[baronfel]

C# 11 will likely ship some form of this in their list patterns. Highlights include:

• list pattern support for any type that is Indexable and Countable

  • ... it has an accessible indexer that takes an Index as an argument or otherwise an accessible indexer with a single int parameter. If both indexers are present, the former is preferred.

• slice support for any type that is countable as well as sliceable:

  • it has an accessible indexer that takes a Range as an argument or otherwise an accessible Slice method with two int parameters. If both are present, the former is preferred.

• able to take a slice over anything that's list-able
• Also supports so-called 'spread' parameters for ranges of specific not-otherwise-matched items: match [0..10] with | [first, ..middle, last] would have first = 0, middle = [1..9], and last = 10

That's a really nice set of rules overall, the one that is the least-doable in F# through some non-compiler-change mechanism is the 'spread pattern'.

[dsyme]

I'm not totally thrilled about adding list patterns to a language, nor indeed most pattern sugar. For list patterns, I think their performance can be really subtle, especially for immutable structures - is the middle copied out or not? That depends very much on whether the data structure supports copy-free inspection into its internals, which in turn likely rest on quite complex and subtle uses of Span and Memory (or simply can't be done at all).

The F# position (also OCaml, and to some extent Haskell) has historically been to avoid the somewhat addictive temptation to add pattern sugar and, for F#, to instead ask users to put all such complexity into active patterns. Active pattern definitions are "normal code" and don't require particularly deep knowledge about how pattern syntax is de-sugared (it's fairly obvious) and can be read "forwards" just like the rest of code. They also encourage the user to write patterns at an appropriate semantic level (for example, combining multiple nested patterns representing a semantic categorization of, say, a list of strings, into one active pattern).

Still, I hear what you're saying @baronfel . It's just I also expect a bit of a backlash to C# list pattern syntax over time, and have long been cautious about adding it to F# for the reasons above.

[smoothdeveloper]

to avoid the somewhat addictive temptation to add pattern sugar

For some reasons, C# seems to be going totally the other way, with predicates that can be expressed in terser way, in some cases, than the F# way (to put all complex stuff behind when).

C# approach seems, in general, to enable some deduplication but I haven't played with it to really get the feel of it.

I also remember, hearing from seasoned haskell developers, that leaning a lot on pattern matching (and DU) had it's limitations in terms of design, because it lead to some possible duplication, when things are matched over and over again.

I also favor caution, as to extend pattern constructs, it would be ok, to see how much C# code start using the feature, and if practially speaking, an active pattern is not good enough, for now, until we know more.

[mrange]

For what's it is worth I am also in favour of a cautious approach. I watch C# feature explosion in pattern matching and wonder if in 2025 the language spec for C# pattern matching will be bigger than for the rest of the language put together. Seems to me that more generic solutions like Active Patterns are preferable over adding a lot of special cases in the language spec.

[gusty]

I think a generic mechanism comes in handy when working with collections like a NonEmptyList<'t> which I use a lot, and it feels a bit awkward to have to define something different (with a different operator or a different active recognizer name) just because the list is not empty. Right now we use Cons(x,xs) for NonEmptyList<'t>.

[JohSand]

The F# position (also OCaml, and to some extent Haskell) has historically been to avoid the somewhat addictive temptation to add pattern sugar and, for F#, to instead ask users to put all such complexity into active patterns. Active pattern definitions are "normal code" and don't require particularly deep knowledge about how pattern syntax is de-sugared (it's fairly obvious) and can be read "forwards" just like the rest of code. They also encourage the user to write patterns at an appropriate semantic level (for example, combining multiple nested patterns representing a semantic categorization of, say, a list of strings, into one active pattern).

Personally, I have no problems writing active patterns for matching on various collections, but as far as I can see, they won't work well for Span, or other byrefs. Since those can only be wrapped in other byrefs, and neither Option, or ValueOption, or Choice are byreflike.

[jwosty]

Perhaps a good compromise would be the ability to write user-defined active pattern infix operators, bonus points if they're overloadable (probably via SRTP)

I'm sure there's already a suggestion for that...

[gusty]

I couldn't agree more. Here is the existing suggestion: https://github.com/fsharp/fslang-suggestions/issues/998