January 2024 - Haskell-Cafe

Re: [Haskell-cafe] Wincomplete-uni-patterns and bidirectional patterns
by Olaf Klinke 18 Jan '24

18 Jan '24

> > Hence I believe that completeness checks in presence of patterns is > > equivalent to determine whether a disjunction of logic formulae, > > which > > are possibly self-referential, is a tautology. That may well be > > semi- > > decidable at best. > > That seems plausible, but I think that interface stability is a more > serious concern. It isn't enough to know that *as-implemented* at a > given time some particular set of patterns is complete. > > The implementation of a set of patterns (or the underlying type) can > change in a manner that changes complete <-> incomplete in either > direction. Such changes are non-breaking, provided there was no > "contract" (COMPLETE pragma) that the patterns are *intended* to be > complete. > You are right: It is possible that the types of the bidirectional patterns do not change, but the completeness changes. In your example given I would argue the contract is broken, because the new patterns are for a different type Foo. Instead -- before: Good, Bad are complete data Foo = A | B pattern Good :: Foo pattern Good = A pattern Bad :: Foo pattern Bad = B -- after: Good, Bad are incomplete -- Foo, Good as before pattern Bad = A Here neither the definition of Foo nor the types of Good or Bad have changed, but completeness has. Here is why I think that completeness checks even with pattern synonyms should work and we would not need COMPLETE pragmas. The algorithm for a set of patterns of type T is: 1. Construct a Stone [1] space X from the given type T. (Often X = T) 2. Translate each pattern to a clopen of that Stone space 3. Use Stone duality to translate coverage into a Zeroth-order logic problem, which is decidable. Let us define an equivalence relation on the elements of a type. Say x~y whenever there is no pattern that can distinguish x and y by pattern match. Notice that any pattern partitions the set of equivalence classes into two disjoint subsets, think of isJust or isNothing. In general, given a pattern Pat for type T, write isPat :: T -> Bool isPat x = case x of Pat -> True _ -> False For functions types, there is only one equivalence class, because there is only one way to pattern-match a function. Observe that two elements can be distinguished by a set of patterns if and only if there is one element in the pattern set that already distinguishes them. Do pattern synonyms refine the equivalence relation induced by ordinary constructors? No. Consider type Clopen x = x -> Bool data C = L C | R C cl :: Clopen C cl = isL . shift where isL :: Clopen C -- a pattern isL (L c) = True isL (R c) = False shift :: C -> C shift (L c) = c shift (R c) = c Can one define a single pattern synonym pattern CL :: C -> C such that CL matches c if any only if cl c == True? Note that cl is the disjunction of two ordinary patterns, namely L (L _) R (L _) CL morally should be the pattern (_(L _)) but that is not valid pattern syntax. Indeed with synonyms we can define the CL pattern: {-# LANGUAGE PatternSynonyms, ViewPatterns #-} swap :: C -> C swap (L (R c)) = R (L c) swap (R (L c)) = L (R c) swap c = c pattern CL c <- (swap -> L c) isCL :: Clopen C isCL c = case c of CL _ -> True _ -> False Now, at least as long as a type X has only a finite number of constructors (integers with numeric literals being an exception), the type Clopen X defines a Stone space, a compact zero-dimensional Hausdorff space. By Stone duality these are dually equivalent to Boolean algebras. The duality translates the problem of coverage by clopens to the problem of proving that the disjunction of some elements in the algebra is the top element 'True'. Since Zeroth-order logic is decidable, completness checks even in the presence of pattern synonyms should be, too. For the countably infinite type C above, one can use the Select monad [2] to decide whether any number of clopens covers the space, pattern or not. For numeric literal patterns we can safely say that any set of patterns is not covering unless a wildcard pattern is among them. Olaf [1] https://en.wikipedia.org/wiki/Stone_space [2] https://hackage.haskell.org/package/transformers-0.6.1.1/docs/Control-Monad… see also https://hackage.haskell.org/package/infinite-search

2 1

Re: [Haskell-cafe] Wincomplete-uni-patterns and bidirectional patterns
by Olaf Klinke 16 Jan '24

16 Jan '24

> > I think the completeness checker works fine in all > > pattern-synonym-free cases, i.e. when you're using only real > > constructors. One can envision a simple recursive divide-and-conquer algorithm, see below. > I don't actually understand why completeness > > annotations are needed for pattern synonyms. > > I remember reading somewhere, but I can't find it now, that GHC's > coverage checker does not look inside pattern synonym definitions at > all, and this is by design: namely to ensure abstraction boundaries. > Looking inside the definition would mean that type checking behaviour > (in a way -- if you count coverage checks as "type checking") of user > code is influenced by invisible implementation details of the > "constructors" they're using. Compare that to 'type' versus 'newtype' on the type level: A type is just an alias, a synonym. The type checker has access to all information on the right hand side of the equality. With extensions like TypeSynonymInstances, A type alias is interchangeable with the aliased type. If what you report is true, they should not have called pattern synonyms a "synonym". > > My own thoughts on this: if GHC would look inside pattern synonym > definitions, then it would be hard to ensure that GHC thinks that > certain things are _not_ complete even if technically they are. For > example, if you have a data type with, say, 3 constructors, but you > hide > some of those (don't export them) and use pattern synonyms to make it > look like 4 constructors, then you might want GHC's coverage checker > to > consider that a data type with 4 constructors, not one with 3. > COMPLETE > pragmas add "positive" information -- "this set is complete, in > addition > to whatever other complete sets GHC might already know" -- and there > is > no way to _subtract_ complete sets from GHC's knowledge base. > > This is mostly me theorising, but perhaps it helps. > > - other Tom > I don't think the number of constructors/patterns is the issue. Likely the problem lies in the fact that while ordinary constructors make up disjoint subsets of the type, with patterns you can define overlapping sets, which makes completeness checks much more complicated. Hence I believe that completeness checks in presence of patterns is equivalent to determine whether a disjunction of logic formulae, which are possibly self-referential, is a tautology. That may well be semi- decidable at best. Olaf

3 2

Re: [Haskell-cafe] Wincomplete-uni-patterns and bidirectional patterns
by Olaf Klinke 16 Jan '24

16 Jan '24

> On Mon, Jan 15, 2024 at 12:00:16PM +0100, Olaf Klinke wrote: > > How can I teach GHC 9 that the pattern is indeed exhaustive? > > Have you tried COMPLETE pragmas? > > > https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/pragmas.html#comple… > > Tom Huh, of course that works. Thanks. It never occurred to me to even consider the existence of manual completeness annotation, since completeness checks work so reliably for ordinary constructors. But maybe my types weren't esoteric enough so far. Are there pattern-free cases where the GHC completeness checker is wrong? Of what computational class is the problem? Can I simulate a Turing machine by checking completeness in the presence of patterns? Olaf

3 2

GSoC 2024 Call for Ideas
by Aaron Allen 16 Jan '24

16 Jan '24

Dear Haskellers, Google Summer of Code is a long-running program by Google that supports Open Source projects. Haskell has been involved in the Google Summer of Code program almost since its inception and we are hoping to participate again in 2024! In order to do this we need a collection of ideas for participants to select from. In the past this has included significant improvements to Haskell projects such as GHC, Cabal, and HLS - and it can include your project as well! This is a great opportunity to find new contributors for your project and many past participants have become involved long-term. You can find more info and instructions on how to participate here: https://summer.haskell.org/ideas.html.

1 0

[Haskell] [ANNOUNCE] Haskell Language Server 2.6.0.0 released
by Zubin Duggal 15 Jan '24

15 Jan '24

Binaries for this release are available at https://downloads.haskell.org/~hls/haskell-language-server-2.6.0.0/. These binaries can be installed using [GHCup](https://www.haskell.org/ghcup/), using the vanilla metadata channel. ```bash ghcup --url-source=https://raw.githubusercontent.com/haskell/ghcup-metadata/master/ghcup-vanilla-0.0.8.yaml install hls 2.6.0.0 ``` All of these tarballs have associated GPG signatures. The signature should be from `Zubin Duggal <zubin(a)well-typed.com>` (key ID [588764FBE22D19C4](https://keys.openpgp.org/search?q=588764FBE22D19C4)) The prebuilt binaries in this release support the following GHC versions: - 9.2.8 - 9.4.8 - 9.6.4 - 9.8.1 # Changelog - Bindists for GHC 9.6.4 - A new semantic tokens plugin (#3892, @soulomoon). - Improvements to multiple home unit support with GHC 9.4. Using cabal 3.11+ will load proper multiple home unit sessions by default, fixing a lot of issues with loading and reloading projects that have more than one component (#3462, @wz1000). - Removed implicit-hie, resulting in better behaviour for projects without cradles. - Don't produce diagnostics for disabled plugins (#3941, @fendor). - Many other bug fixes. Happy editing! - Zubin.

1 0

Wincomplete-uni-patterns and bidirectional patterns
by Olaf Klinke 15 Jan '24

15 Jan '24

Dear Cafe, I have a data type with a bidirectional pattern {-# LANGUAGE PatternSynonyms #-} newtype T f t = C (f Double) pattern T :: Double -> T Identity t pattern T x = C (Identity x) Note that pattern T is the only way to construct something of type (T Identity t) for any phantom parameter t. When using the pattern to match in a where clause, the Wincomplete-uni-pattern warns me about non-exhaustive pattern matches that are in fact matched: f a = x where T x = g a :: T Identity () warning: [-Wincomplete-uni-patterns] Pattern match(es) are non- exhaustive in a pattern binding: Patterns not matched: C (Identity _) Minimal complete example is attached. How can I teach GHC 9 that the pattern is indeed exhaustive? GHC seems to have only three issues involving incomplete-uni-patterns, only one of them open, none of which matches my observations. Thanks Olaf

3 2

Fully-funded PhD studentship in functional programming
by Graham Hutton 15 Jan '24

15 Jan '24

Dear all, I'm advertising a fully-funded PhD studentship in functional programming, starting 1st October 2024. Please pass the advert on to anyone who may be intersted in applying. Best wishes, Graham Hutton +-----------------------------------------------------------+ Fully-Funded PhD Studentship Functional Programming Lab School of Computer Science University of Nottingham, UK http://tinyurl.com/fplab-phd Applications are invited for a fully-funded PhD studentship under the supervision of Prof Graham Hutton, starting on 1st October 2024. The successful applicant will join the Functional Programming Lab, an internationally-leading centre for programming language research. The topic for the studentship is open, but should relate to the research interests of Prof Hutton on the mathematics of program construction. The studentship forms part of the recently-funded EPSRC project on Semantics-Directed Compiler Construction, which seeks to develop new techniques for constructing certified compilers from semantics. The studentship is open to home and international students, is fully-funded for three and a half years, and includes a stipend of £18,622 per year and tuition fees. Applicants are expected to have a first-class Masters or Bachelors degree (or equivalent) in Computer Science and/or Mathematics, and an excellent ability and interest in the mathematical foundations of programming, together with experience of programming in a functional language. Further information and advice for prospective applicants is available from http://tinyurl.com/369xwzc7. Funding for this studentship is already in place. To apply, please submit the following items by email to graham.hutton(a)nottingham.ac.uk: (1) a brief covering letter that describes your reasons for wishing to undertake a PhD and any ideas you have about potential topics; (2) a copy of your CV, including your actual or expected degree class(es) and results of all university examinations; (3) an example of your technical writing, such as a report or dissertation; (4) email addresses for two academic referees. Closing date for applications: Friday 9th February 2024. +-----------------------------------------------------------+ — Professor Graham Hutton School of Computer Science University of Nottingham, UK http://www.cs.nott.ac.uk/~pszgmh This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please contact the sender and delete the email and attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham. Email communications with the University of Nottingham may be monitored where permitted by law.

1 0

2nd Call for Participation: BOB 2024 (Berlin, Mar 15, Early Bird until Jan 30)
by Stefan Wehr 15 Jan '24

15 Jan '24

========================================================================= BOB 2024 Conference “What happens if we simply use what’s best?” March 15, 2024, Berlin https://bobkonf.de/2024/ Program: https://bobkonf.de/2024/program.html Registration: https://bobkonf.de/2024/registration.html ========================================================================= BOB conference is a place for developers, architects, and decision-makers to explore technologies beyond the mainstream in software development and to find the best tools available to software developers today. Our goal is for all participants of BOB to return home with new insights that enable them to improve their own software development experience. The program features 14 talks and 8 tutorials on current topics: https://bobkonf.de/2024/program.html Talk subjects includes functional programming, property-based testing, service API design, programming for spacecraft, accessibility, hypermedia, business processes, software analytics, event-based communication and zero-knowledge proofs. BOB will feature tutorials on F#, Haskell, Lean, SwiftUI, Copilot, the K Framework, functional domain modelling, and Liberating Structures. Andreas Rossberg will give the keynote talk. Registration is open - online tickets are all under 200€, and many discount options are available, as are grants for members of groups underrepresented in tech. Early-bird registration runs until Jan 30: https://bobkonf.de/2024/registration.html

1 0

Fastest saturating add?
by amindfv＠mailbox.org 14 Jan '24

14 Jan '24

I have a function that's called many (many) times, which involves a saturating addition (addition without overflow). In other words, I'd like ((254 :: Word8) + 10) to equal 255 (which is maxBound::Word8), not 8 (which is what you get with overflow). My current code, without particular regard to performance, is simply: satAdd :: Word8 -> Word8 -> Word8 satAdd x y = let m = x + y in if m < x then 255 else m This seems like the type of code somebody's already worked on the performance for, though I can't find much Haskell-specific in searches online. Is there a faster way to do this? Thanks! Tom

2 1

restore type from existential
by zoran.bosnjak＠via.si 10 Jan '24

10 Jan '24

Dear haskellers, if for example I have the following (simplified) situation: import GHC.TypeLits type MyTypes = '[ () -- index 0 , Char -- index 1 , Int -- index 2 ] data SNat (n :: Nat) where SZ :: SNat 0 SS :: SNat n -> SNat (n+1) data Wrap where WrapUnsafe :: SNat n -> t -> Wrap t1 = WrapUnsafe SZ () :: Wrap t2 = WrapUnsafe (SS SZ) 'x' :: Wrap t3 = WrapUnsafe (SS (SS SZ)) (1::Int) :: Wrap Is it possible to have an 'unwrap' function? That is: to combine MyType types table and the type index... to get the exact type back. Something in the form: unwrapUnsafe :: Wrap -> t unwrapUnsafe (WrapUnsafe (ix::SNat n) (val::t)) = undefined x1 = unwrapUnsafe t1 x2 = unwrapUnsafe t2 x3 = unwrapUnsafe t3 GHC didn't like any of my attempt. Is it even possible? regards, Zoran

3 5