- Glasgow-haskell-users

Type-level Replicate function
by Bas van Dijk 21 Nov '14

21 Nov '14

Hi, tl;dr How do I implement a type-level Replicate function that takes a (n :: Nat) and a type e and produces a type-level list of n e elements. The rest of my email gives some background on why I need this, how it's supposed to be used and my current erroneous implementation. I'm presenting it as a Haskell program: {-# LANGUAGE TypeOperators #-} {-# LANGUAGE DataKinds #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE GADTs #-} import GHC.TypeLits import Data.Type.Equality import Data.Type.Bool -- For work I'm implementing a binary protocol for -- communicating with some device. I need to be able to send -- a packet of orders to a device. -- -- An order is a list of addresses and command to send to -- these addresses. -- -- After sending the packets of orders the device should -- send back a packet of replies. The packet of replies -- should have a reply for each command send to each -- address. -- -- I would like to make the latter requirement apparent in -- the types so that when I send a packet of orders the type -- will tell me what packet of replies to expect. -- -- So I introduce the OrderPacket type which is -- parameterised with a type-level lists of commands: data OrderPacket (cmds :: [*]) where -- The empty packet: NoOrders :: OrderPacket '[] -- Extending an existing packet with an order. -- -- The (n :: Nat) in Order denotes the number of -- addresses to send the command to. Note that because I -- expect n command replies back I need to create a -- type-level list of n commands and prepend that to the -- existing commands: (:>) :: !(Order n command) -> !(OrderPacket commands) -> OrderPacket (Replicate n command :++: commands) -- As explained, an Order is a vector of addresses of length -- n paired with a command: data Order (n :: Nat) command where Order :: (Command command) => !(Addresses n) -> !command -> Order n command -- In my real implementation this class describes how to -- encode / decode commands: class Command command -- This is the typical Vector of length n type specialised -- to Address: data Addresses (n :: Nat) where Nil :: Addresses 0 (:*:) :: !Address -> !(Addresses n) -> Addresses (n+1) infixr 5 :*: type Address = Int -- Append two type-level lists. type family (rs1 :: [*]) :++: (rs2 :: [*]) :: [*] type instance '[] :++: rs2 = rs2 type instance (r ': rs1) :++: rs2 = r ': (rs1 :++: rs2) -- I'm currently using the following Replicate type-level -- function: type family Replicate (n :: Nat) r :: [*] type instance Replicate (n :: Nat) r = If (n == 0) '[] (r ': Replicate (n-1) r) -- However when I write some code like the following: isNull :: OrderPacket cmds -> Bool isNull NoOrders = True isNull (orderMsg :> orderMsgs) = False -- I get the following error: src/TypeLevelReplicate.hs:49:9: Type function application stack overflow; size = 201 Use -ftype-function-depth=N to increase stack size to N GHC.TypeLits.EqNat (((n-1)-1)-1)...) 0 ~ (((n-1)-1)-1)...) == 0) In the pattern: orderMsg :> orderMsgs In an equation for ‘isNull’: isNull (orderMsg :> orderMsgs) = True Failed, modules loaded: none. -- Note that when I adapt my code to use my own type-level -- inductive implementation of natural numbers like: data N = Z | S N type family Replicate (n :: N) r :: [*] type instance Replicate Z r = '[] type instance Replicate (S n) r = r ': Replicate n r -- I don't get the type function application stack overflow. Any hints on how to make this work with Nats from GHC.TypeLits? Thanks, Bas

2 2

Re: Type-level Replicate function
by Dr. ÉRDI Gergő 21 Nov '14

21 Nov '14

I've replaced the definition of Replicate with a closed type family, and now isNull typechecks on 7.8.2: type family Replicate (n :: Nat) t : [*] where Replicate 0 t = '[] Replicate n t = t ': Replicate (n-1) t On Nov 21, 2014 3:52 PM, "Bas van Dijk" <v.dijk.bas(a)gmail.com> wrote: Hi, tl;dr How do I implement a type-level Replicate function that takes a (n :: Nat) and a type e and produces a type-level list of n e elements. The rest of my email gives some background on why I need this, how it's supposed to be used and my current erroneous implementation. I'm presenting it as a Haskell program: {-# LANGUAGE TypeOperators #-} {-# LANGUAGE DataKinds #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE GADTs #-} import GHC.TypeLits import Data.Type.Equality import Data.Type.Bool -- For work I'm implementing a binary protocol for -- communicating with some device. I need to be able to send -- a packet of orders to a device. -- -- An order is a list of addresses and command to send to -- these addresses. -- -- After sending the packets of orders the device should -- send back a packet of replies. The packet of replies -- should have a reply for each command send to each -- address. -- -- I would like to make the latter requirement apparent in -- the types so that when I send a packet of orders the type -- will tell me what packet of replies to expect. -- -- So I introduce the OrderPacket type which is -- parameterised with a type-level lists of commands: data OrderPacket (cmds :: [*]) where -- The empty packet: NoOrders :: OrderPacket '[] -- Extending an existing packet with an order. -- -- The (n :: Nat) in Order denotes the number of -- addresses to send the command to. Note that because I -- expect n command replies back I need to create a -- type-level list of n commands and prepend that to the -- existing commands: (:>) :: !(Order n command) -> !(OrderPacket commands) -> OrderPacket (Replicate n command :++: commands) -- As explained, an Order is a vector of addresses of length -- n paired with a command: data Order (n :: Nat) command where Order :: (Command command) => !(Addresses n) -> !command -> Order n command -- In my real implementation this class describes how to -- encode / decode commands: class Command command -- This is the typical Vector of length n type specialised -- to Address: data Addresses (n :: Nat) where Nil :: Addresses 0 (:*:) :: !Address -> !(Addresses n) -> Addresses (n+1) infixr 5 :*: type Address = Int -- Append two type-level lists. type family (rs1 :: [*]) :++: (rs2 :: [*]) :: [*] type instance '[] :++: rs2 = rs2 type instance (r ': rs1) :++: rs2 = r ': (rs1 :++: rs2) -- I'm currently using the following Replicate type-level -- function: type family Replicate (n :: Nat) r :: [*] type instance Replicate (n :: Nat) r = If (n == 0) '[] (r ': Replicate (n-1) r) -- However when I write some code like the following: isNull :: OrderPacket cmds -> Bool isNull NoOrders = True isNull (orderMsg :> orderMsgs) = False -- I get the following error: src/TypeLevelReplicate.hs:49:9: Type function application stack overflow; size = 201 Use -ftype-function-depth=N to increase stack size to N GHC.TypeLits.EqNat (((n-1)-1)-1)...) 0 ~ (((n-1)-1)-1)...) == 0) In the pattern: orderMsg :> orderMsgs In an equation for ‘isNull’: isNull (orderMsg :> orderMsgs) = True Failed, modules loaded: none. -- Note that when I adapt my code to use my own type-level -- inductive implementation of natural numbers like: data N = Z | S N type family Replicate (n :: N) r :: [*] type instance Replicate Z r = '[] type instance Replicate (S n) r = r ': Replicate n r -- I don't get the type function application stack overflow. Any hints on how to make this work with Nats from GHC.TypeLits? Thanks, Bas _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users(a)haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

2 1

NOTE: the primary webserver is going down for immediate maintenance.
by Austin Seipp 19 Nov '14

19 Nov '14

Hello *, The primary haskell.org domain, www.haskell.org, is hosted on a system which seems to have lost one of its RAID disks completely. We were planning on moving this machine in the next few weeks to new infrastructure, but we are now expediting this plan and will be doing it ASAP. As we move this server, both the webserver and the mailing system will be going down. Please don't be alarmed if your emails aren't delivered or things go quiet. Many services will continue to work, but we do realize this will be upsetting for many. You can follow the progress on #haskell-infrastructure on Freenode, and see updates on https://status.haskell.org If you need to download something like a GHC binary or Haskell Platform package, you can use https://downloads.haskell.org in the mean time, which is a new service we were hoping to announce more officially soon, but is already working today. Unfortunately we cannot give an expected time of completion for the move, but we'll try to keep people well informed through IRC or something like Reddit. Thanks -- Regards, Austin Seipp, Haskell Consultant Well-Typed LLP, http://www.well-typed.com/

2 1

RE: The future of the Haskell98 and Haskell2010 packages
by Austin Seipp 18 Nov '14

18 Nov '14

Hello all, A few weeks ago, I opened up a discussion about a particular GHC bug, #9590. This bug is concerned with the future of the Haskell98 and Haskell2010 packages, which try to embody their two respective Haskell standards. They do this by shipping the 'exact library specification' that the standards have. In our discussion this past week between me, SimonM, SPJ, Herbert and Mikolaj, we came to this discussion again since the 7.10 STABLE freeze is almost here, and it seems to have puttered out. In this discussion, we came to the conclusion we think these packages should be removed from GHC for the 7.10 release. To be clear, this was not a 100% unanimous decision or formal vote; SimonM and I supported removal, while everyone else seemed to be rather undecided or ambivalent. Most of the proposed alternative solutions seemed somewhat one-off. Furthermore, we didn't find a solution that wouldn't either A) require some amount of GHC modifications (possibly indefinitely into the future) to support these packages, or B) changing the definitions in these packages to deviate from the standard. Instead, we proposed that we instead overhaul part of the GHC users manual, and clearly outline our deviations from the Haskell 2010 standard library. To be clear: GHC can still typecheck, compile, and efficiently execute Haskell 2010 code. It is merely the distribution of compatible packages that has put us in something of a bind. Furthermore, we aren't aware of any other compilers/platforms like ours that try to maintain such stringent separation of these packages, and furthermore, both of the haskell{98,2010} packages have a fairly small number of reverse dependencies. I'd like to hear what people think about this. It seems likely I will move forward on this by the end of the week unless we face very strong opposition to this idea, or someone is willing to fix #9590 somehow for us. -- Regards, Austin Seipp, Haskell Consultant Well-Typed LLP, http://www.well-typed.com/

4 4

More flexible literate Haskell extensions (Trac #9789), summary on wiki
by Merijn Verstraaten 16 Nov '14

16 Nov '14

As requested on my ticket I summarised the entire proposal on the wiki here: https://ghc.haskell.org/trac/ghc/wiki/FlexibleLiterateExtension I don't expect a lot of disagreement on discussion, aside from minor bike shedding on the flavour of the extension. I've started implementing this already. I'm open to bikesheds on exact extension, as it shouldn't affect the implementation. Unless there's any vehement objections, I'll produce a diff on fabricator asap. Cheers, Merijn

3 5

Re: More flexible literate Haskell extensions (Trac #9789), summary on wiki
by Simon Hengel 14 Nov '14

14 Nov '14

On Fri, Nov 14, 2014 at 03:53:13PM +0800, Simon Hengel wrote: > > Can you explain why this would not solve your usecase? i.e., why would > > README.lhs.md not suffice? > > I haven't tried, but my assumption was that this is not picked up by > GitHub. I just verified, GitHub dose not pick up README.lhs.md files as READMEs, meaning that a README.lhs.md file will not be rendered as a projects README file on GitHub. Cheers, Simon

1 0

Re: More flexible literate Haskell extensions (Trac #9789), summary on wiki
by Jan Stolarek 14 Nov '14

14 Nov '14

.lhs = Literate Haskell So maybe .mhs = Markdown Haskell instead of .lhs+md? Jan

1 0

Rules for class methods and Safe Haskell
by Wolfgang Jeltsch 13 Nov '14

13 Nov '14

Hi, the module Control.Arrow declares a set of rules for the Arrow class. It is marked “Trustworthy”, probably to allow these rules to actually fire. Now these rules are only correct for class instances that actually satisfy the arrow laws. If the author of another module defines an instance of Arrow that does not respect the laws, this other module could still be considered “Safe” by GHC, although the rules from Control.Arrow are bogus now. Is this considered a problem? All the best, Wolfgang

2 2

Under what conditions are finalizers not run?
by Wolfgang Jeltsch 13 Nov '14

13 Nov '14

Hi, the documentation of System.Mem.Weak under <http://hackage.haskell.org/package/base-4.7.0.1/docs/System-Mem-Weak.html> says the following: > It is not guaranteed that a finalizer will eventually run, and no > attempt is made to run outstanding finalizers when the program exits. In which situations are finalizers not run? I see that they might not be run when the program ends while the weak pointer is still alive, but are there also other situations? The above quote seems to say that even an implementation that ignores any finalizers would conform to the API specification. I think it is actually quite bad if you do not have any guarantees about when finalizers are run. In the memo table example, for instance, this would mean that the memo table could grow very large, which would not just result in bad space complexity, but also bad time complexity for lookups. I am actually particularly interested in adding finalizers to IORefs. Are there any stronger guarantees for finalizers attached to IORefs and MVars? All the best, Wolfgang

1 0

RFC: Dropping Windows XP support
by Austin Seipp 13 Nov '14

13 Nov '14

Hi all, This is a quick discussion about the current system requirements for Windows builds. Spurred by a recent[1] LLVM discussion, I'd like to raise the question of dropping support for Windows XP, and bumping the minimum required version to Windows Vista or even Windows 7. For one, Microsoft doesn't support XP anymore, so most people are moving off it anyway. 'Soon' even XP Embedded will be obsoleted. But second, Vista and beyond introduced useful new APIs we could use. I was digging through the LLVM thread and two came out to me: 1) We could switch to using slim reader/writer locks, which in some workloads may work out better than critical sections (they'll win on more read-heavy workloads). The downsides is there's no recursive locking but we don't use that anyway (and recursive locks are considered bad by many anyway[2]). 2) We could probably use an actual condition variables API that was introduced with Vista. Currently we use a giant EVENT object to emulate the API, which could be replaced with the real deal. Both of these could be nice wins for simplicity and performance I think. I know there are some corporate users out there who this may impact, and users as well. I'd like to know what people think. Particularly what version we should standardize on. FWIW, I don't plan on changing any of this until the 7.12 release at least. [1] http://article.gmane.org/gmane.comp.compilers.llvm.devel/78419 [2] http://www.zaval.org/resources/library/butenhof1.html -- Regards, Austin Seipp, Haskell Consultant Well-Typed LLP, http://www.well-typed.com/

5 4