Upgrade to Pro — share decks privately, control downloads, hide ads and more …

大規模数値計算を支える Haskell ── Pragmatic Haskell in Lar...

Hiromi Ishii
November 09, 2019

大規模数値計算を支える Haskell ── Pragmatic Haskell in Large-Scale Numerical Computation──

Haskell Day 2019 での講演抄録です。

Hiromi Ishii

November 09, 2019
Tweet

More Decks by Hiromi Ishii

Other Decks in Technology

Transcript

  1. w 'PVOEFEJO+VMZ *KPJOFEUIJTTQSJOH w 0VS(PBM(FOFSBM1VSQPTF 6MUSBIJHITQFFE -BSHFTDBMF /VNFSJDBM4PMWFS w (FOFSBM1VSQPTF$BOTJNVMBUF"/:QIZTJDBM

    QIFOPNFOBFYQSFTTFEBT%J⒎FSFOUJBM&RVBUJPOT w 4QFFE4DBMF#JMMJPODFMMTºWBMTº.4UFQT
 #GSFFEPNº.JMMJPO4UFQT
  2. w 'PVOEFEJO+VMZ *KPJOFEUIJTTQSJOH w 0VS(PBM(FOFSBM1VSQPTF 6MUSBIJHITQFFE -BSHFTDBMF /VNFSJDBM4PMWFS w (FOFSBM1VSQPTF$BOTJNVMBUF"/:QIZTJDBM

    QIFOPNFOBFYQSFTTFEBT%J⒎FSFOUJBM&RVBUJPOT w 4QFFE4DBMF#JMMJPODFMMTºWBMTº.4UFQT
 #GSFFEPNº.JMMJPO4UFQT w 0VSTPMWFSJTDVSSFOUMZXSJUUFOJO -JOFTPG)BTLFMM  BOEDPOTJTUTPGQBDLBHFT
  3. "HHSFTTJWF6TFPG()$ TypeApplications FlexibleContexts MPTC DataKinds TypeFamilies ScopedTypeVariables FlexibleInstances TypeOperators UndecidableInstances

    DerivingStrategies OverloadedStrings PolyKinds TemplateHaskell RecordWildCards GND 0 50 100 150 200 5PUBM.PEVMFT &YUFOTJPOT 0O()$
  4. "HHSFTTJWF6TFPG()$ TypeApplications FlexibleContexts MPTC DataKinds TypeFamilies ScopedTypeVariables FlexibleInstances TypeOperators UndecidableInstances

    DerivingStrategies OverloadedStrings PolyKinds TemplateHaskell RecordWildCards GND 0 50 100 150 200 5PUBM.PEVMFT &YUFOTJPOT 0O()$ 8FBSFVTJOHGFBUVSFTJOUSPEVDFEJO
 QuantifiedConstraints, DerivingVia, Source Plugins
  5. 0VS(PBMTBOE)BTLFMM w (FOFSBM1VSQPTF4PMWFS w %FQFOEFOU)BTLFMM w 5BHMFTT'JOBMBOE*OJUJBM4UZMF w 4QFFEBOE4DBMF w

    1SJNJUJWF.POBET 3FXSJUJOH3VMFT 4QFDJBMJTBUJPO *OUFSQSPDFTT DPNNVOJDBUJPO w .POBEJD4FRVFODF"CTUSBDUJPOUPNBLFVTFPGUIFTF w 1MVHJOTVTJOH&YUFOTJCMF3FDPSET w "OENBOZPUIFSUFDIOJRVFTOPUNFOUJPOFEUIJTUBML &YQSFTTJWJUZ4BGFUZ .PEVMBSJUZ &YUFOTJCJMJUZ
  6. 0VS(PBMTBOE)BTLFMM w (FOFSBM1VSQPTF4PMWFS w %FQFOEFOU)BTLFMM w 5BHMFTT'JOBMBOE*OJUJBM4UZMF w 4QFFEBOE4DBMF w

    1SJNJUJWF.POBET 3FXSJUJOH3VMFT 4QFDJBMJTBUJPO *OUFSQSPDFTT DPNNVOJDBUJPO w .POBEJD4FRVFODF"CTUSBDUJPOUPNBLFVTFPGUIFTF w 1MVHJOTVTJOH&YUFOTJCMF3FDPSET w "OENBOZPUIFSUFDIOJRVFTOPUNFOUJPOFEUIJTUBML &YQSFTTJWJUZ4BGFUZ
  7. &YBNQMFT#PVOEBSZ4BOJUZ BOE2VBOUJUZ/BNF w 8FUSFBUTPNBOZEJ⒎FSFOULJOETPGRVBOUJUJFT w WFMPDJUZ UFNQFSBUVSF FMFDUSJDDIBSHF w 4PNFPGUIFNTIBSFTUIFTBNFSFQSFTFOUBUJPO

    CVUUIFZ BSFDPNQMFUFMZEJ⒎FSFOURVOBUJUJFT w "OEUIFZSFRVJSFTEJ⒎FSFOUQSFQSPDFTTJOHPGCPVOEBSZ WBMVFTUPFOGPSDFJOWBSJBOUT
  8. &YBNQMFT#PVOEBSZ4BOJUZ BOE2VBOUJUZ/BNF w 8FUSFBUTPNBOZEJ⒎FSFOULJOETPGRVBOUJUJFT w WFMPDJUZ UFNQFSBUVSF FMFDUSJDDIBSHF w 4PNFPGUIFNTIBSFTUIFTBNFSFQSFTFOUBUJPO

    CVUUIFZ BSFDPNQMFUFMZEJ⒎FSFOURVOBUJUJFT w "OEUIFZSFRVJSFTEJ⒎FSFOUQSFQSPDFTTJOHPGCPVOEBSZ WBMVFTUPFOGPSDFJOWBSJBOUT w 1SPDFTTFEWBMVFTNVTUOPUCFBEEFENVMUJQMJFEXJUIPUIFS WBMVFT CFDBVTFJUDBOWJPMBUFJOWBSJBOUT
  9. &YBNQMFT#PVOEBSZ4BOJUZ BOE2VBOUJUZ/BNF w 8FUSFBUTPNBOZEJ⒎FSFOULJOETPGRVBOUJUJFT w WFMPDJUZ UFNQFSBUVSF FMFDUSJDDIBSHF w 4PNFPGUIFNTIBSFTUIFTBNFSFQSFTFOUBUJPO

    CVUUIFZ BSFDPNQMFUFMZEJ⒎FSFOURVOBUJUJFT w "OEUIFZSFRVJSFTEJ⒎FSFOUQSFQSPDFTTJOHPGCPVOEBSZ WBMVFTUPFOGPSDFJOWBSJBOUT w 1SPDFTTFEWBMVFTNVTUOPUCFBEEFENVMUJQMJFEXJUIPUIFS WBMVFT CFDBVTFJUDBOWJPMBUFJOWBSJBOUT ‎ 4MPHBO)VNBOTGPSHFU-FUUZQFTSFNFNCFS
  10. 5BHHJOHXJUI2VBOUJUZ/BNFBOE 4BOJUZ w TagQty name s: BRVBOUJUZOBNFEnameXJUIQSPDFTTFETUBUFs. w *OUIJTXBZ BUZQFEFQFOETPOWBMVFTnameBOETBOJUZ

    :FU%POF B %FQFOEFOU5ZQF w 8FDBOVTF,OPXO/BUMJLFDPOTUSBJOUTUPSFJGZUZQFMFWFMWBMVFTUPFYQSFTTJPO w 4JODFXFXBOUUPBMMPXPQFSBUJPOTPOMZPOYetRVBOUJUJFT XFQSPWJEFNumsPOMZ GPSYets BOEIJEFDPOTUSVDUPSTGSPNPUIFSNPEVMFT w /VNJOTUBODFJTJOEFQPGLBOEOBNF XFDBOKVTUXSJUFBQPMZNPSQIJDJOTUT data Sanity = Yet | Done newtype TagQty name (s  Sanity) = TQty { unTagQty  PhysQty } unproc  TagQty k t 'Done  TagQty t 'Yet class Processable env k name where process  env  PhysQty  TagQty name 'Done instance s ~ 'Yet  Num (TagQty k name s)
  11. 5ZQFDIFDLFS1MVHJO w 8FBMTPVTFUZQFMFWFMOBUVSBMTUPNBJOUBJOJOHFHEJNFOTJPOT w 1SPCMFN()$DBOOPUTFF  GPSOPODPODSFUF WBSJBCMFL  w

    8FDBOVTFFYJTUJOH5ZQF$IFDLFS1MVHJOTUPUFMM()$UIBUTVDI DPOTUSBJOUTIPME w 8FVTFghc-typelits-natnormalise[4]. w &WFOUIPVHIJUDBOTPMWFFRVBUJPOBMDPOTUSBJOUTPOMZ CVUJUTV⒏DFT BOEJUTFFNTFYUFOTJPOUPOPOFRVBUJPOBMPOFJTOPUTPIBSE . {-# OPTIONS_GHC -fplugin GHC.TypeLits.Normalise #-}
 {-# OPTIONS_GHC -fplugin-opt ( ):allow-negated-numbers #-} (k + 1) − 1 = k
  12. 4VNNBSZ-FU5ZQFT 3FNFNCFS w )VNBOTGPSHFUJOWBSJBOUT-FUUZQFTSFNFNCFS w 8JUI%BUB,JOET POFDBOFOGPSDFJOWBSJBOUTTUBUJDBMMZ BUUZQF MFWFM BMMPXTPQFSBUJPOTPOMZPOUIFTBNFEFHT

    POMZPO VOQSPDFTTFERUZT BOETPPO  w 4VDIQBSBNFUFSTXIJDIEPFTOUPDDVSJOBDUVBMWBMVFJTDBMMFE QIBOUPNUZQFT w ()$JTOPUTPDMFWFSUPTPMWFUSJWJBMDPOTUSBJOUT CVUPOFDBOBVHNFOU UIFNXJUIUZQFDIFDLFSQMVHJOT
  13. 4VNNBSZ-FU5ZQFT 3FNFNCFS w )VNBOTGPSHFUJOWBSJBOUT-FUUZQFTSFNFNCFS w 8JUI%BUB,JOET POFDBOFOGPSDFJOWBSJBOUTTUBUJDBMMZ BUUZQF MFWFM BMMPXTPQFSBUJPOTPOMZPOUIFTBNFEFHT

    POMZPO VOQSPDFTTFERUZT BOETPPO  w 4VDIQBSBNFUFSTXIJDIEPFTOUPDDVSJOBDUVBMWBMVFJTDBMMFE QIBOUPNUZQFT w ()$JTOPUTPDMFWFSUPTPMWFUSJWJBMDPOTUSBJOUT CVUPOFDBOBVHNFOU UIFNXJUIUZQFDIFDLFSQMVHJOT w /PUFGPS1SPGFTTJPOBMT8FBSFUSZJOHIBSEUPBWPJEUPVTFTJOHMFUPOT
  14. 0VS(PBMTBOE)BTLFMM w (FOFSBM1VSQPTF4PMWFS w %FQFOEFOU)BTLFMM w 5BHMFTTpOBMBOE*OJUJBM4UZMF w 4QFFEBOE4DBMF w

    1SJNJUJWF.POBET 3FXSJUJOH3VMFT 4QFDJBMJTBUJPO *OUFSQSPDFTT DPNNVOJDBUJPO w .POBEJD4FRVFODF"CTUSBDUJPOUPNBLFVTFPGUIFTF w 1MVHJOTVTJOH&YUFOTJCMF3FDPSET w "OENBOZPUIFSUFDIOJRVFTOPUNFOUJPOFEUIJTUBML &YQSFTTJWJUZ4BGFUZ
  15. 0VS(PBMTBOE)BTLFMM w (FOFSBM1VSQPTF4PMWFS w %FQFOEFOU)BTLFMM w 5BHMFTTpOBMBOE*OJUJBM4UZMF w 4QFFEBOE4DBMF w

    1SJNJUJWF.POBET 3FXSJUJOH3VMFT 4QFDJBMJTBUJPO *OUFSQSPDFTT DPNNVOJDBUJPO w .POBEJD4FRVFODF"CTUSBDUJPOUPNBLFVTFPGUIFTF w 1MVHJOTVTJOH&YUFOTJCMF3FDPSET w "OENBOZPUIFSUFDIOJRVFTOPUNFOUJPOFEUIJTUBML .PEVMBSJUZ
  16. .POBEEFMJNJUTUBTLT w "GUFSBMNPTUIBMGBOZFBS UIFTUSVDUVSFIBTDIBOHFEUJNFCZUJNF w #VUUIFTUBUFNFOUDBOTUJMMIPMEUSVFJOBTFOTF w 5ZQF$MBTTFT GPMMPXJOHUBHMFTTpOBMBQQSPBDI BCTUSBDUT

    FBDITFQBSBUFUBTLT w %J⒎FSFOUJBMPQFSBUJPOT DBMDVMBUJPOTDIFNBUB *0  w &RVBUJPOXSJUFSTIBTUPDBSFBCPVUPOMZBCTUSBDUEJ⒎FSFOUJBM PQFSBUJPOTPOMZ
  17. .POBEEFMJNJUTUBTLT w "GUFSBMNPTUIBMGBOZFBS UIFTUSVDUVSFIBTDIBOHFEUJNFCZUJNF w #VUUIFTUBUFNFOUDBOTUJMMIPMEUSVFJOBTFOTF w 5ZQF$MBTTFT GPMMPXJOHUBHMFTTpOBMBQQSPBDI BCTUSBDUT

    FBDITFQBSBUFUBTLT w %J⒎FSFOUJBMPQFSBUJPOT DBMDVMBUJPOTDIFNBUB *0  w &RVBUJPOXSJUFSTIBTUPDBSFBCPVUPOMZBCTUSBDUEJ⒎FSFOUJBM PQFSBUJPOTPOMZ w #BDLFOE 4PMWFS XSJUFSTDBOJNQMFNFOUUIFNDPODSFUFMZ  MFBWJOHFRVBUJPOTUIFNTFMWFTVOUPVDIFE
  18. 5BHMFTT'JOBM4UZMF<> data family PhysQty m class Monad m  MonadDiff

    m where grad  PhysQty m  m (PhysQty m) div  PhysQty m  m (PhysQty m) w "CTUSBDUDPNNPOPQFSBUJPOBTBNPOBEJDGVODUJPO w "DUVBMMZ diffOFFETTPNFHFPNFUSJDJOGPBTBOFYUSBBSHVNFOU  CVUJUJTIJEEFOJOMonadic value m w 5IJTIJEFTUIFJNQMEFUBJMPGEJ⒎PQTBOEFOBCMFTVTUPTFQBSBUFJNQM GSPNBCTUSBDUFRVBUJPOT5IJTFODPVSBHFTNPEVMBSJUZBOEHFOFSBMJUZ
  19. 0VUDPNFNVMUJQMF CBDLFOET w 0OFDBOJNQMFNFOUBOETXJUDINVMUJQMFTPMWFSTFBTJMZ w 8JUIPVUSFXSJUJOHUIFFYJTUJOHEJ⒎FSFOUJBMFRVBUJPOT w $VSSFOUMZXFIBWF4PMWFSTJTPNPSQIJDUPQVSFReader envBOEReaderT env

    IO w 5IFMBUUFSJTDBMMFE3*0QBUUFSOJO)BTLFMMDPNNVOJUZ w (JWFTVTVOJGPSNUSFBUNFOUGPSCPUIJNNVUBCMF TUBUFTZFUSFUBJOJOHUISFBEBOEFYDFQUJPOTBGFUZ
  20. 0VUDPNFNVMUJQMF CBDLFOET w 0OFDBOJNQMFNFOUBOETXJUDINVMUJQMFTPMWFSTFBTJMZ w 8JUIPVUSFXSJUJOHUIFFYJTUJOHEJ⒎FSFOUJBMFRVBUJPOT w $VSSFOUMZXFIBWF4PMWFSTJTPNPSQIJDUPQVSFReader envBOEReaderT env

    IO w 5IFMBUUFSJTDBMMFE3*0QBUUFSOJO)BTLFMMDPNNVOJUZ w (JWFTVTVOJGPSNUSFBUNFOUGPSCPUIJNNVUBCMF TUBUFTZFUSFUBJOJOHUISFBEBOEFYDFQUJPOTBGFUZ w 8FVTFDerivingViaUPSFEVDFCPJMFSQMBUFDPEFTGPS TVDIJOTUBODFT
  21. 1SPCMFN5PP.VDI#JOET ν △ u − 1 ρ grad P (-)

     ((nu *)  laplacian u)  ((/rho)  grad u) 1SPCMFN)BWFUPXSJUF( )UPDPNQPTFGVODUJPOT
  22. 1SPCMFN5PP.VDI#JOET w 8FVTF("%5T JOJUJBMSFQS UPQSPWJEFTNBSU DPOTUSVDUPST ν △ u −

    1 ρ grad P (-)  ((nu *)  laplacian u)  ((/rho)  grad u) 1SPCMFN)BWFUPXSJUF( )UPDPNQPTFGVODUJPOT
  23. 1SPCMFN5PP.VDI#JOET w 8FVTF("%5T JOJUJBMSFQS UPQSPWJEFTNBSU DPOTUSVDUPST w 5IFZBMTPUBLFTDBSFPGBEEJUJPOBMQSFQPTU QSPDFTTFTGPSFBDIEJ⒎FSFOUJBMPQFSBUPST ν

    △ u − 1 ρ grad P (-)  ((nu *)  laplacian u)  ((/rho)  grad u) 1SPCMFN)BWFUPXSJUF( )UPDPNQPTFGVODUJPOT
  24. *OJUJBM3FQSFTFOUBUJPO w 'SFF 0QFSBUJPOBM .POBEBOETNBSUDPOT VTJOH("%5T w %J⒎FSFOUJBMPQFSBUPSTDBOBDDFQUBOZUFSNXIJDIDBOCF DBTUFEUPUIFJSJOUFOEFEBSHVNFOUT data

    Expr m a where Join  Expr m (Expr m a)  Expr m a Grad  (ToPhysQty m qty)  Expr m qty  Expr m (PhysQty m) grad'  (ToPhysQty m a)  a  Expr m (PhysQty m) grad' = Grad . toExpr -- pre-process for conversion
  25. &YBNQMF stokesEqn u ρ p = eval $ (1 /:

    ρ) .*: (eta .*: laplace' u -: grad' p) ∂u ∂t = 1 ρ (η ▵ u − grad P) "MNPTU-JUFSBM5SBOTMBUJPOJOUPUIF$PEF 㾎0OFEPFTOUIBWFUPLOPXBCPVUBOZ JNQMFNFOUBUJPOEFUBJMUPXSJUFFRVBUJPOT
  26. 5BHMFTTpOBM4VNNBSZ w 4FQBSBUFTBSFBPGUBTLTCZNPOBEJDPQFSBUJPOT  FOBCMJOHUPDPODFOUSBUFPOUIFJSPXOCVTJOFTT w &RVBUJPOXSJUFSTEPOUIBWFUPDBSFBCPVUJNQM EFUBJM w 8FFYQMPJUTJNJMBSUFDITUPEFMJNJUNBOZPUIFS

    UBTLTFRVBUJPO PQFSBUJPOJNQM DBDIJOH JOUFS QSPDFTTDPNNVOJDBUJPO w 8FDBOVTFJOJUJBMSFQSFTFOUBUJPOUPFMJNJOBUF CJOEIFMMJOUBHMFTTpOBMTUZMF
  27. 0VS(PBMTBOE)BTLFMM w (FOFSBM1VSQPTF4PMWFS w %FQFOEFOU)BTLFMM w 5BHMFTT'JOBMBOE*OJUJBM3FQSFTFOUBUJPO w 4QFFEBOE4DBMF w

    1SJNJUJWF.POBET 3FXSJUJOH3VMFT 4QFDJBMJTBUJPO *OUFSQSPDFTT DPNNVOJDBUJPO w .POBEJD4FRVFODF"CTUSBDUJPOUPNBLFVTFPGUIFTF w 1MVHJOTVTJOH&YUFOTJCMF3FDPSET w "OENBOZPUIFSUFDIOJRVFTOPUNFOUJPOFEUIJTUBML .PEVMBSJUZ
  28. 0VS(PBMTBOE)BTLFMM w (FOFSBM1VSQPTF4PMWFS w %FQFOEFOU)BTLFMM w 5BHMFTT'JOBMBOE*OJUJBM3FQSFTFOUBUJPO w 4QFFEBOE4DBMF w

    1SJNJUJWF.POBET 3FXSJUJOH3VMFT 4QFDJBMJTBUJPO *OUFSQSPDFTT DPNNVOJDBUJPO w .POBEJD4FRVFODF"CTUSBDUJPOUPNBLFVTFPGUIFTF w 1MVHJOTVTJOH&YUFOTJCMF3FDPSET w "OENBOZPUIFSUFDIOJRVFTOPUNFOUJPOFEUIJTUBML
  29. 4FRVFOUJBMUZQFTJO)BTLFMM w 1IZTJDBMWBMVFTBSFFYQSFTTFEBTTFRVFODFTPGSFBMT w 8IJDI4FRVFODFUZQFNVTUXFVTF  w -JTUTHJWFOJO1SFMVEF TJNQMFBOEEFDMBSBUJWF*'CVU4-08 JOEFYJOH

    BENJUT'VTJPO w 7FDUPST'BTU 0  JOEFYJOHXJUIEFDMBSBUJWF*' F⒏DJFOU TUPSBHFGPS6OCPYFEUZQFT BENJUT'VTJPO 5FNQFSBUVSFT Cell #0 #1 #2 #3 ʜʜ 273K 273K 300K 450K
  30. 4USFBN'VTJPO< > w 'VODUJPOTPOTFRVFODFTBUJTpFTTPNFBMHFCSBJDMBXT XIJDIGVTFT NVMUJQMFMPPQJOUPPOFQBTT w VectorsFYQMPJUTVDISFMBUJPOTUPPQUJNJTFGVODUJPOT w 5IFZPODFDPOWFSUWFDUPSTUPBCTUSBDUStreamTBOEBundleT

    w 4USFBNBNPOBEJDHFOFSBUJOHGVODUJPO w #VOEMF4USFBN PQUJPOBMDPODSFUFWFDUPSWBMVFBOEMFOHUI JOGPSNBUJPO w TUSFBNVOTUSFBNGVODUJPOTDPOWFSUT7FDUPSTUPGSPN#VOEMFT f z ∘ g ≡ (f ∘ g) z
  31. 1SPCMFN.BOZLJOETPG WFDUPS w #PYFEDBOTUPSFBOZUZQFT w 6OCPYFEDBOTUPSF TVNPGQSPEVDUTPG VOCPYFE UZQFTFH*OU %PVCMF

    #PPM w 4UPSBCMFGPSDPNNVOJDBUJPOTXJUI$MJCSBSZ w BOENPOPNPSQIJDOFXUZQFXSBQQFSTBSPVOEUIFN w 1SPCMFN8FXBOUUPUSFBUUIFNVOJGPSNMZ w $BOXFEPUIJTSFUBJOJOHF⒏DJFODZPGWFDUPST
  32. 'JSTU"UUFNQU type family Elem seq type family Key seq class

    Monad m  MSeq m seq where imap  (Key seq  Elem seq  Elem seq)  seq m seq index  Index seq  seq  m (Elem seq) ifoldr  (Key seq  Elem seq  Elem seq)   accum   instance Monad m  MSeq m (Vector a) instance Monad m  MSeq m (VecMap k a) .POBEJDSFTVMU w 1SPCMFN.POBEJDSFTVMUNJHIUTBDSJpDFTUSFBNGVTJPO w 1SPCMFN)BWFUPJNQMFNFOUWFDUPSPQFSBUJPOTBMMCZIBOET .BOZPUIFSPQT
  33. "OTXFSTUSFBNVOTUSFBN w "MNPTUBMMWFDUPSPQFSBUJPOTBSFJOEFFEJNQMEBT DPNQPTJUJPOTPGTUSFBNVOTUSFBNXJUI4USFBN #VOEMFPQFSBUJPOT w 4JODF4USFBN#VOEMFTBSFNPOBEJDCZEFGBVMUBOE UIFZGVTFTXFMM XFDBOHFUF⒏DJFODZGPSGSFF w

    5IFSVMFstream ◦ unstream ≡ returnSFEVDFT JOUFSOBMUFSNTFWFOJGUIFSFTVMUJTNPOBEJD w 0OFDBOBMTPQSPWJEFBO*'UPGVTFEJ⒎FSFOULJOEPG WFDUPSTJOUPPOF
  34. 3FTVMU type family VecRep seq  Type  Type class

    (Monad m)  MSequence m seq where unfoldrM  (s  m (Maybe (Elem seq, s)))  s  m seq indexM'  seq  Int  m (Elem seq) stream'  seq  B.Bundle m (VecRep seq) (Elem seq) unstream'  B.Bundle m (VecRep seq) (Elem seq)  m seq
  35. 3FTVMU type family VecRep seq  Type  Type class

    (Monad m)  MSequence m seq where unfoldrM  (s  m (Maybe (Elem seq, s)))  s  m seq indexM'  seq  Int  m (Elem seq) stream'  seq  B.Bundle m (VecRep seq) (Elem seq) unstream'  B.Bundle m (VecRep seq) (Elem seq)  m seq w "MMPUIFSPQFSBUJPOTBSFEFSJWFEGSPNUIFTFQSJNJUJWFTXJUI Data.Vector.Fusion.Bundle.MonadicNPEVMF
  36. 3FTVMU type family VecRep seq  Type  Type class

    (Monad m)  MSequence m seq where unfoldrM  (s  m (Maybe (Elem seq, s)))  s  m seq indexM'  seq  Int  m (Elem seq) stream'  seq  B.Bundle m (VecRep seq) (Elem seq) unstream'  B.Bundle m (VecRep seq) (Elem seq)  m seq w "MMPUIFSPQFSBUJPOTBSFEFSJWFEGSPNUIFTFQSJNJUJWFTXJUI Data.Vector.Fusion.Bundle.MonadicNPEVMF w 0OFDBOFYQMPJUGVTJPOSVMFTQSPWJEFECZWFDUPSQBDLBHFGPSGSFF
  37. 3FTVMU type family VecRep seq  Type  Type class

    (Monad m)  MSequence m seq where unfoldrM  (s  m (Maybe (Elem seq, s)))  s  m seq indexM'  seq  Int  m (Elem seq) stream'  seq  B.Bundle m (VecRep seq) (Elem seq) unstream'  B.Bundle m (VecRep seq) (Elem seq)  m seq w "MMPUIFSPQFSBUJPOTBSFEFSJWFEGSPNUIFTFQSJNJUJWFTXJUI Data.Vector.Fusion.Bundle.MonadicNPEVMF w 0OFDBOFYQMPJUGVTJPOSVMFTQSPWJEFECZWFDUPSQBDLBHFGPSGSFF w #POVT)FUFSPHFOFPVT$PNCJOBUPSTBOE1SJN.POBEPQUJNJTBUJPO
  38. #POVT)FUFSPHFOFPVT $PNCJOBUPST w 0OFDBONBQ[JQEJ⒎FSFOULJOEPGTUSFBNTJOPOFQBTT w 8FQSPWJEF3FXSJUF3VMFTUPFMJNJOBUFDPOWFSTJPOPWFSIFBET XIFOTPNFPGBSHVNFOUTIBWFUIFTBNFWFDUPSSFQSFTFOUBUJPO hzipWith  (MSeq

    m s, MSeq m t, MSeq m u, Key s ~ Key t, Key s ~ Key u)  (Elem s  Elem t  Elem u)  s  t  m u hzipWithM f = \as bs  unstream $ B.zipWithM f (B.reVector $ stream as) (B.reVector $ stream bs)
  39. #POVT%FTUSVDUJWF "TTJHONFOUTBSF:PVS'SJFOET w MSeqBTTVNFTUIFJSSFUVSOUZQFUPCFNPOBEJD w 5IFSFJTBDMBTTPG.POBETBENJUUJOHEFTUSVDUJWF BTTJHONFOUT PrimMonad GSPNprimitiveQBDLBHF w

    1SPWJEFTBDPNNPO*'GPSSTBOEIONPOBETBOE NPOBEUSBOTGPSNFSTBSPVOEUIFN w *GVOEFSMZJOHNPOBEmJTPrimMonad POFDBOVTFUIFJS BCJMJUZGPSNVUBCMFSFGFSFODFTUPHBJOQFSGPSNBODF
  40. VOTUSFBNXJUI1SJN.POBE w *GNJTPrimMonad JOQBSUJDVMBSJGIOXJUIFYUSBUSBOTGPSNFS MBZFSTPOUPQ XFDBOVTFNVUBCMFPQFSBUJPOTPOUIFNUPHFU WFDUPSTJOTUBOUMZ w 5IJTHBWFVTYTQFFEVQTJOQSBDUJDF &YBDUSFDPSETBSF

    MPTUTPSSZ  ‎ $PNQPTFTXFMMXJUIUBHMFTTpOBMBQQSPBDI unstreamPrimM  (PrimMonad m, Vector (VRep s) (Elem s), VRep s (Elem seq) ~R# seq)  B.Bundle m u (Element s)  m s unstreamPrimM s = coerce  (G.unsafeFreeze  MG.munstream s) {-# RULES "unstreamM[IO]" unstreamM = unstreamPrimM #-}
  41. .POBEJD4FRVFODFBOE 1SJN.POBE4VNNBSZ w 4USFBN'VTJPOSFEVDFTDPOTUBOUPWFSIFBETJHOJpDBOUMZ w &YQMPJUJOHvectorT4USFBN#VOEMF'VTJPONFDIBOJTN XPSLTMJLFBDIBSN w "MTPFOBCMFTUPGVTFEJ⒎FSFOULJOEPGWFDUPST w

    3FXSJUJOH3VMFTDBOIFMQSFEVDFPWFSIFBEIFSF w *GUIFSFTVMUUZQFJTNPOBEJD UIFOPOFDBOFYQMPJU1SJN.POBE JOTUBODFUPHBJONPSFTQFFE SFUBJOJOHEFDMBSBUJWFNBOOFS w 5IJTDPNQPTFTXFMMXJUIUBHMFTTpOBMTUZMFBQQSPBDI  JNQMFNFOUFEXJUI3*0QBUUFSO w %FTUSVDUJWFBTTJHONFOUT EJTHVJTFEBTEFDMBSBUJWF DPNCJOBUPST BSFJOEFFEZPVSGSJFOET
  42. 0VS(PBMTBOE)BTLFMM w (FOFSBM1VSQPTF4PMWFS w %FQFOEFOU)BTLFMM w 5BHMFTT'JOBMBOE*OJUJBM3FQSFTFOUBUJPO w 4QFFEBOE4DBMF w

    1SJNJUJWF.POBET 3FXSJUJOH3VMFT 4QFDJBMJTBUJPO *OUFSQSPDFTT DPNNVOJDBUJPO w .POBEJD4FRVFODF"CTUSBDUJPOUPNBLFVTFPGUIFTF w 1MVHJOTVTJOH&YUFOTJCMF3FDPSET w "OENBOZPUIFSUFDIOJRVFTOPUNFOUJPOFEUIJTUBML
  43. 0VS(PBMTBOE)BTLFMM w (FOFSBM1VSQPTF4PMWFS w %FQFOEFOU)BTLFMM w 5BHMFTT'JOBMBOE*OJUJBM3FQSFTFOUBUJPO w 4QFFEBOE4DBMF w

    1SJNJUJWF.POBET 3FXSJUJOH3VMFT 4QFDJBMJTBUJPO *OUFSQSPDFTT DPNNVOJDBUJPO w .POBEJD4FRVFODF"CTUSBDUJPOUPNBLFVTFPGUIFTF w 1MVHJOTVTJOH&YUFOTJCMF3FDPSET w "OENBOZPUIFSUFDIOJRVFTOPUNFOUJPOFEUIJTUBML &YUFOTJCJMJUZ
  44. .PUJWBUJPO1MVHJO .FDIBOJTN w 5BHMFTTpOBMTUZMFBMMPXFEVTUPXSJUFNVMUJQMF 4PMWFSTOJDFMZ w CVUUIFPGTPMWFSTFWFOUVBMMZJODSFBTFE BOE JUIBECFDPNFIBSEUPNBJOUBJOBMMPGUIFN w

    *UJTEFTJSBCMFGPSVTUPIBWFPOMZBMJNJUFEOVNCFS PG4PMWFSTBOEFYUFOEUIFNCZ1MVHJOTGPS NPEVMBSJUZBOENBJOUBJOBCJMJUZ
  45. .PUJWBUJPO1MVHJO .FDIBOJTN w 5BHMFTTpOBMTUZMFBMMPXFEVTUPXSJUFNVMUJQMF 4PMWFSTOJDFMZ w CVUUIFPGTPMWFSTFWFOUVBMMZJODSFBTFE BOE JUIBECFDPNFIBSEUPNBJOUBJOBMMPGUIFN w

    *UJTEFTJSBCMFGPSVTUPIBWFPOMZBMJNJUFEOVNCFS PG4PMWFSTBOEFYUFOEUIFNCZ1MVHJOTGPS NPEVMBSJUZBOENBJOUBJOBCJMJUZ w 8IBUTOFFEFEGPSUIFN
  46. 1MVHJO4QFD class Plugin p where data PState p  Type

    data PConfig p  Type type POutput p  Type type PlugM p (m  *  *)  Constraint pluginOptionP  OptParser (PConfig p) setupState  MonadIO m  PConfig p  m (PState p) initialise  (p ∈ ps, MonadPlugins ps m, PlugM p m)  proxy p  Info  m Info finalise  (p ∈ ps, MonadPlugins ps m, PlugM p m)  proxy p  Info  m Info genOutput  (p ∈ ps, MonadPlugins ps m, PlugM p m)  PConfig p  m (POutput p)
  47. #VOEMJOHNVMUJQMFQMVHJO EBUBUPPOF w 8FSFQSFTFOUUIF4PMWFSNPOBETXJUIQMVHJOTQTBTB4PMWFS QT XIFSFQTJTBUZQFMFWFMMJTUPGQMVHJOT data PStateBundle ps =

    PSB { p  PState p | p ∈ ps } w 0OFDBOTJNVMBUFTVDIEBUBUZQFTXJUI )JHIFS,JOEFE  &YUFOTJCMF3FDPSET JOUIJTDBTF ),)-JTUTV⒏DFT UIPVHI w "OFOUJSF4PMWFSXJUIQMVHJOTpsNVTULFFQJOGP BTTPDJBUFEUPFBDIQMVHJOBTBCVOEMF TPNFUIJOHMJLF Solver '[] -- Solver without any Plugin 
 Solver '[A, B, C] -- Solver with Plugins A, B and C
  48. &YUFOTJCMF3FDPSET w )BTLFMMT3FDPSE-BCFMTBOE7BMVFTBSFpYFE w &YUFOTJCMF3FDPSETPOFDBOEZOBNJDBMMZBEEEFMFUF  DPOTUSBJOpFMETBOEUSFBUQPMZNPSQIJDBMMZ SFUBJOJOHUZQFTBGFUZ w 'PSFBDIp

    ∈ ps  PState p WBMVFJOstates  PStateB psDBOCF SFUSJFWFECZstates ^. hfieldL @p w 5IFSFBSFQMFOUZPGFYJTUJOHMJCT extensible, vinyl, superrecords,FUD  GPSFYUSFDTCVUXFJNQMECZPVSTFMWFTGPSTPNFSFBTPOT w ),%PQT TVDIBTCGPMES.CGPMEM. .FNCFSDPOTUS DBOCFVTFEUP QSPDFTTCVOEMFTCBDLXBSEGPSXBSE type PBundle h ps = Record h (IdentFields ps) type PStateB ps = PBundle PState ps
  49. 8IZDVTUPNMJCSBSZ w *UNVTUTBUJTGZUIFGPMMPXJOHTBUUIFTBNFUJNF w 'BTU"DDFTT*OUFSOBMSFQSNVTUCFBSSBZWFDUPS OPUMJOLFE MJTU w -JHIU1BDLBHF%FQFOEFODZXFOFFEPOMZXIBUXFOFFE w

    1PMZNPSQIJD-BCFMXFXBOUUPMBCFMpFMETXJUIBSCJUSBSZ UZQFT OPUOFDFTTBSJMZDPOWFSUJCMFUP4ZNCPMTPS/BUT w ),%MJLFPQFSBUJPOTOFFEFEGPSWBSJPVTGPMEJOHNBQQJOH PQFSBUJPOTFHTFSJBMJTBUJPO JOJUJBMJTBUJPO
  50. 8IZDVTUPNMJCSBSZ w *UNVTUTBUJTGZUIFGPMMPXJOHTBUUIFTBNFUJNF w 'BTU"DDFTT*OUFSOBMSFQSNVTUCFBSSBZWFDUPS OPUMJOLFE MJTU w -JHIU1BDLBHF%FQFOEFODZXFOFFEPOMZXIBUXFOFFE w

    1PMZNPSQIJD-BCFMXFXBOUUPMBCFMpFMETXJUIBSCJUSBSZ UZQFT OPUOFDFTTBSJMZDPOWFSUJCMFUP4ZNCPMTPS/BUT w ),%MJLFPQFSBUJPOTOFFEFEGPSWBSJPVTGPMEJOHNBQQJOH PQFSBUJPOTFHTFSJBMJTBUJPO JOJUJBMJTBUJPO w 0VSMJCBMTPQSPWJEFT()$1MVHJOT BMMPXJOHUPXSJUF3FDPSE DPOTUSVDUJPOOBUVSBMMZBOESFEVDFTUIFBNPVOUPGIBOE XSJUUFOQSPPGT
  51. #FGPSF5D1MVHJO (&%~)  forall l xs h a. Member l

    (Labels xs)  Record h xs  l := (h (ElemAt (Idx l (Labels xs)) (Vals xs))  h a)  Record h ((l  a) |< xs) Record hl &%~ (_ := f) = Record $ gcastWith (takeMapApply @Entry' @(Index l (Labels xs)) @xs) $ gcastWith (dropMapApply @Entry' @(Index l (Labels xs) + 1) @xs) $ gcastWith (mapApplyAppend @Entry' @(Take (Index l (Labels xs)) xs) @((l  a) ': Drop (Index l (Labels xs) + 1) xs) ) $ hmodify' (Proxy @(Index l (Labels xs))) f hl 5SJWJBMIBOEXSJUUFOQSPPGT .BQI YT ZT .BQIYT .BQIZT 
  52. #FGPSF5D1MVHJO (&%~)  forall l xs h a. Member l

    (Labels xs)  Record h xs  l := (h (ElemAt (Idx l (Labels xs)) (Vals xs))  h a)  Record h ((l  a) |< xs) Record hl &%~ (_ := f) = Record $ gcastWith (takeMapApply @Entry' @(Index l (Labels xs)) @xs) $ gcastWith (dropMapApply @Entry' @(Index l (Labels xs) + 1) @xs) $ gcastWith (mapApplyAppend @Entry' @(Take (Index l (Labels xs)) xs) @((l  a) ': Drop (Index l (Labels xs) + 1) xs) ) $ hmodify' (Proxy @(Index l (Labels xs))) f hl 5SJWJBMIBOEXSJUUFOQSPPGT .BQI YT ZT .BQIYT .BQIZT 
  53. "GUFS5D1MVHJO {-# OPTIONS_GHC -fplugin Data.TypeLevel.List.Solver #-} (&%~)  forall l

    xs h a. Member l (Labels xs)  Record h xs  l := (h (ElemAt (Idx l (Labels xs)) (Vals xs))  h a)  Record h ((l  a) |< xs) Record hl &%~ (_ := f) = Record $ hmodify' (Proxy @(Index l (Labels xs))) f hl
  54. 4PVSDF1MVHJO {-# LANGUAGE OverloadedLabels #-} record = emptyRec &+ #a

    := 42 &+ #b := False &+ #c := () {-# OPTIONS_GHC -fplugin Data.Record.Plugin #-} {-# LANGUAGE OverloadedLabels #-} record = MkRecord { a = 42  Int, b = False, c = () } 8JUIPVU4PVSDF1MVHJO 8JUI4PVSDF1MVHJO w 0WFSMPBEJOHGPS3FDPSEVQEBUFBOEBDDFTTPSTZOUBYDBOOPUCF JNQMFNFOUFEXJUIUIFDVSSFOU()$4PVSDF1MVHJO.FDIBOJTN
  55. 1MVHJOT4VNNBSZ w &YUFOTJCMF3FDPSETBSFQBSUJDVMBSMZVTFGVMGPS1MVHJOT w ),%PQFSBUJPOT TVDIBTIFUFSPGPMETBOENBQT DBOCFVTFEUP JNQMJOJUJBMJTBUJPOTFSJBMJTBUJPO w /PUPOMZ),%T

    CVUTJNQMFWBMVFMFWFMGPMEJOHPGUZQFMFWFMMJTUT JTBMTPVTFGVM w "LJOEPGSPXQPMZNPSQIJTNDBOBMTPCFVTFEUPUSFBUBCVOEMFPG QIZTJDBMRVBOUJUJFTQPMZNPSQIJDBMMZ
  56. 1MVHJOT4VNNBSZ w &YUFOTJCMF3FDPSETBSFQBSUJDVMBSMZVTFGVMGPS1MVHJOT w ),%PQFSBUJPOT TVDIBTIFUFSPGPMETBOENBQT DBOCFVTFEUP JNQMJOJUJBMJTBUJPOTFSJBMJTBUJPO w /PUPOMZ),%T

    CVUTJNQMFWBMVFMFWFMGPMEJOHPGUZQFMFWFMMJTUT JTBMTPVTFGVM w "LJOEPGSPXQPMZNPSQIJTNDBOBMTPCFVTFEUPUSFBUBCVOEMFPG QIZTJDBMRVBOUJUJFTQPMZNPSQIJDBMMZ w 8FEFWJTFEDVTUPN&YU3FDMJCSBSZXJUI
  57. 1MVHJOT4VNNBSZ w &YUFOTJCMF3FDPSETBSFQBSUJDVMBSMZVTFGVMGPS1MVHJOT w ),%PQFSBUJPOT TVDIBTIFUFSPGPMETBOENBQT DBOCFVTFEUP JNQMJOJUJBMJTBUJPOTFSJBMJTBUJPO w /PUPOMZ),%T

    CVUTJNQMFWBMVFMFWFMGPMEJOHPGUZQFMFWFMMJTUT JTBMTPVTFGVM w "LJOEPGSPXQPMZNPSQIJTNDBOBMTPCFVTFEUPUSFBUBCVOEMFPG QIZTJDBMRVBOUJUJFTQPMZNPSQIJDBMMZ w 8FEFWJTFEDVTUPN&YU3FDMJCSBSZXJUI w 1PMZNPSQIJDMBCFMT GBTUJOEFYJOH BVUPNBUJDDPOTUSBJOUTPMWJOH BTTJTUFECZ5ZQFDIFDLFSQMVHJOT
  58. $PODMVTJPOT w )BTLFMMDBOCFVTFEBDIJFWFTJNVMUBOFPVTMZ w )JHIQFSGPNBODFBOE  w "CTUSBDU IJHIMZFYUFOTJCMF HFOFSBMQVSQPTFTPGUXBSF

    w ()$T%FQFOEFOU5ZQFTIFMQTFYUFOTJCJMJUZBOELFFQJOHJOWBSJBOUT w )VNBOT'PSHFU-FU5ZQFT3FNFNCFS w %FQFOEFOU5ZQFTBOE%FTUSVDUJWF"TTJHONFOUTBSFZPVSGSJFET w 8FBSFQMBOOJOHUPQVCMJTIJOUFSOBMMJCSBSJFT JOOPUTPGBSGVUVSF  IPQFGVMMZ  w 4UJMM UIFSFBSFNBOZUIJOHTUPCFJNQSPWFE
  59. #JCMJPHSBQIZ  Oleg Kiselyov, Tagless-final style. http:// okmij.org/ftp/tagless-final/index.html 2. D.

    Coutts, R. Leshchinskiy and D. Stewart, Stream Fusion: From Lists to Streams to Nothing at All. 3. G. Mainland, R. Leshchinskiy and SPJ, Exploiting Vector Instructions with Generalized Stream Fusion. 4. ghc-typelits-natnormalise package
  60. "OZ2VFTUJPOT w )BTLFMMDBOCFVTFEBDIJFWFTJNVMUBOFPVTMZ w )JHIQFSGPNBODFBOE  w "CTUSBDU IJHIMZFYUFOTJCMF HFOFSBMQVSQPTFTPGUXBSF

    w ()$T%FQFOEFOU5ZQFTIFMQTFYUFOTJCJMJUZBOELFFQJOHJOWBSJBOUT w )VNBOT'PSHFU-FU5ZQFT3FNFNCFS w %FQFOEFOU5ZQFTBOE%FTUSVDUJWF"TTJHONFOUTBSFZPVSGSJFET w 8FBSFQMBOOJOHUPQVCMJTIJOUFSOBMMJCSBSJFT JOOPUTPGBSGVUVSF  IPQFGVMMZ  w 4UJMM UIFSFBSFNBOZUIJOHTUPCFJNQSPWFE