wip-tree.hs

#!/usr/bin/env stack
-- stack script --resolver lts-16.11 --package bytestring --package vector --package vector-algorithms --package containers --package array --package primitive

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}

-- {-# LANGUAGE TypeFamilies #-}
-- {-# LANGUAGE FlexibleInstances #-}

-- {{{ Imports

module Main (main) where

import Control.Applicative
import Control.Monad
import Control.Monad.Fix
import Control.Monad.Primitive
import Control.Monad.ST
import Data.Char
import Data.List
import Data.Maybe

{- ORMOLU_DISABLE -}

-- bytestring: https://www.stackage.org/lts-16.11/package/bytestring-0.10.10.0
import qualified Data.ByteString.Builder as BSB
import qualified Data.ByteString.Char8 as BS

-- vector: https://www.stackage.org/lts-16.11/package/vector-0.12.1.2
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM

{- ORMOLU_ENABLE -}

-- }}}

-- {{{ Segment tree

class SegmentTree a where
    type M :: * -> *
    updateParent :: a -> Int -> Int -> M Int
    updateNode :: a -> Int -> M Int

-- | `SegmentTree` of sums (Range Maximum Queries)
newtype RMQ s = RMQ (VM.MVector s Int)

type IORMQ = RMQ RealWorld
type STRMQ s = RMQ s

-- TODO: コンパイルが通ったら `(PrimState m) =>` に変更
instance SegmentTree (RMQ RealWorld) where
    type M = IO
    updateParent x y = undefined
    updateNode x = undefined

-- }}}

getLineIntList :: IO [Int]
getLineIntList = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

getLineIntVec :: IO (VU.Vector Int)
getLineIntVec = VU.unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

main :: IO ()
main = do
  [n, q] <- getLineIntList
  return ()

{- デフォルトのエラー
<PATH>.hs:45:5: error:
    • Illegal family declaration for ‘M’
        Enable TypeFamilies to allow indexed type families
    • In the class declaration for ‘SegmentTree’
   |
45 |     type M :: * -> *
   |     ^^^^^^^^^^^^^^^^
-}

{- `TypeFamilies` を有効化した場合のエラー

<PATH>.hs:44:1: error:
    • The associated type ‘M’
      mentions none of the type or kind variables of the class ‘SegmentTree a’
    • In the class declaration for ‘SegmentTree’
   |
44 | class SegmentTree a where
   | ^^^^^^^^^^^^^^^^^^^^^^^^^...

<PATH>.hs:56:10: error:
    • Illegal instance declaration for ‘SegmentTree (RMQ RealWorld)’
        (All instance types must be of the form (T a1 ... an)
         where a1 ... an are *distinct type variables*,
         and each type variable appears at most once in the instance head.
         Use FlexibleInstances if you want to disable this.)
    • In the instance declaration for ‘SegmentTree (RMQ RealWorld)’
   |
56 | instance SegmentTree (RMQ RealWorld) where
   |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^
-}