sjoerdvisscher / fmlist Goto Github PK

GHC 8.4.1-alpha1 was announced. While testing Agda with this version of GHC, I got an error on fmlist (master branch) related to a missing instance of Semigroup.

This error is reported as a warning in GHC 8.0.2/8.2.2 using the -Wsemigroup flag:

$ cabal install --force-reinstalls --ghc-options='-Wsemigroup -Werror'

So, fixing this warning on GHC 8.0.2/8.2.2 fix the error on GHC 8.4.1-alpha1.

Blocking agda/agda#2878.

last $ join zip (fromList [1..n]) seems, empirically, to be taking something like quadratic time. Thanks to the left-biased nature of zipWith, I don't think we can do much better than the obvious:

zipWith f xs ys = fromList $ L.zipWith f (toList xs) (toList ys)

It's not at all obvious what transformCS actually does. Could you possibly explain? It's also not obvious to me why it's used rather than "naive" implementations. We certainly can write things like

take         :: (Ord n, Num n) => n -> FMList a -> FMList a
-- This is (essentially) what's in GHC.List, when transformed by
-- rewrite rules.
take n xs
  | 0 < n
  = foldr go (`seq` nil) xs n
  | otherwise
  = nil
  where
    go x r m = case m of
      1 -> one x
      _ -> x `cons` r (m - 1)

takeWhile    :: (a -> Bool) -> FMList a -> FMList a
takeWhile p  = foldr go nil
  where
    go x r
      | p x = x `cons` r
      | otherwise = nil

drop         :: (Ord n, Num n) => n -> FMList a -> FMList a
drop n xs | n <= 0 = xs
drop n0 xs0  = foldr go (`seq` nil) xs0 n0
  where
    go x r 0 = x `cons` r 0
    go x r n = r (n - 1)

Is there an efficiency advantage to the transformCS way?