Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Unit #105

Closed
meooow25 opened this issue Aug 23, 2024 · 8 comments · Fixed by #106
Closed

Add Unit #105

meooow25 opened this issue Aug 23, 2024 · 8 comments · Fixed by #106

Comments

@meooow25
Copy link
Contributor

Please consider adding a Unit type:

newtype Unit = Unit { runUnit :: () }

instance Semigroup Unit where
  (<>) = seq

instance Monoid Unit where
  mempty = Unit ()

This makes it possible to writes instances conveniently using folds. Some examples:

instance NFData1 [] where
  liftRnf f = runUnit . foldMap (Unit . f)

-- from containers
instance NFData2 Map where
  liftRnf2 f g = runUnit . foldMapWithKey (\k x -> Unit (f k `seq` g x))

See related: #18
Unit here is the UnitLTR type defined there. However, #18 only uses it internally. This issue is about exporting the type so users can use it freely.

@mixphix
Copy link
Collaborator

mixphix commented Aug 24, 2024

NFData1 [] is already written as a fold.

instance NFData1 [] where
  liftRnf f = foldr (\x r -> f x `seq` r) ()

@mixphix mixphix closed this as completed Aug 24, 2024
@meooow25
Copy link
Contributor Author

meooow25 commented Aug 24, 2024

That's not the point. [] was only an example to show how it may be used.

The aim is to make it easier for other people to define instances on their structures, for which they already have a fold.

@mixphix
Copy link
Collaborator

mixphix commented Aug 24, 2024

Is it impossible to use foldlWithKey or foldrWithKey in the issue you mentioned? I fail to see how exposing a Unit type from deepseq will be of much additional benefit.

@meooow25
Copy link
Contributor Author

foldMap-like functions can be more efficient than foldr or foldl, depending on the structure and implementations. This is the case with Map, for one.

@mixphix
Copy link
Collaborator

mixphix commented Aug 24, 2024

Are you sure that a strict foldMap is more efficient? The entire structure must be reduced to RNF. I haven't seen proof that this monoid is any more efficient than traversing the structure leftwards or rightwards.

@meooow25
Copy link
Contributor Author

meooow25 commented Aug 24, 2024

Sure, if you'd like proof, here are some benchmarks.

Source code
import Control.DeepSeq
import Data.Map (Map)
import qualified Data.Map as M
import Test.Tasty.Bench -- requires tasty-bench

main :: IO ()
main = defaultMain
  [ env (pure m_) $ \m -> bgroup ""
    [ bench "rnfFoldr" $ whnf rnfFoldr m
    , bcompare "rnfFoldr" $ bench "rnfFoldMap" $ whnf rnfFoldMap m
    ]
  ]
  where
    m_ = M.fromList [(i,i) | i <- [1..100000]] :: Map Int Int

rnfFoldr :: (NFData k, NFData a) => Map k a -> ()
rnfFoldr = M.foldrWithKey (\k x z -> rnf k `seq` rnf x `seq` z) ()

rnfFoldMap :: (NFData k, NFData a) => Map k a -> ()
rnfFoldMap = runUnit . M.foldMapWithKey (\k x -> Unit (rnf k `seq` rnf x))

newtype Unit = Unit { runUnit :: () }

instance Semigroup Unit where
  (<>) = seq

instance Monoid Unit where
  mempty = Unit ()

With GHC 9.6.3 and -O, I get

    rnfFoldr:   OK
      294  μs ±  25 μs,   0 B  allocated,   0 B  copied,  18 MB peak memory
    rnfFoldMap: OK
      209  μs ±  11 μs,   0 B  allocated,   0 B  copied,  18 MB peak memory, 0.71x

I should also mention that providing monoids that represent some binary operation is not unusual. See the various newtypes provided in Data.Monoid.

@mixphix
Copy link
Collaborator

mixphix commented Aug 25, 2024

I wouldn't be opposed to a PR closing #18, as long as the code continues to support the same versions.

@mixphix mixphix reopened this Aug 25, 2024
@meooow25
Copy link
Contributor Author

I'll make a PR to add the Unit type.

Personally I don't feel inclined to add rnfFoldableLTR or rnfFoldableRTL, they are too limited in where they can be used.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants