src/Streamly/Enumeration.hs · streamly

git.iko.soy/streamly

on 3ce574a help sign in

streamly/src/Streamly/Enumeration.hs

550 lines 20 kB history raw

1{-# LANGUAGE CPP #-}

3-- |

4-- Module : Streamly.Enumeration

6--

7-- License : BSD3

8-- Maintainer : harendra.kumar@gmail.com

9-- Stability : experimental

10-- Portability : GHC

11--

12-- The functions defined in this module should be rarely needed for direct use,

13-- try to use the operations from the 'Enumerable' type class

14-- instances instead.

15--

16-- This module provides an 'Enumerable' type class to enumerate 'Enum' types

17-- into a stream. The operations in this type class correspond to similar

18-- perations in the 'Enum' type class, the only difference is that they produce

19-- a stream instead of a list. These operations cannot be defined generically

20-- based on the 'Enum' type class. We provide instances for commonly used

21-- types. If instances for other types are needed convenience functions defined

22-- in this module can be used to define them. Alternatively, these functions

23-- can be used directly.

25module Streamly.Enumeration

26 (

27 Enumerable (..)

29 -- ** Enumerating 'Bounded' 'Enum' Types

30 , enumerate

31 , enumerateTo

32 , enumerateFromBounded

34 -- ** Enumerating 'Enum' Types not larger than 'Int'

35 , enumerateFromToSmall

36 , enumerateFromThenToSmall

37 , enumerateFromThenSmallBounded

39 -- ** Enumerating 'Bounded' 'Integral' Types

40 , enumerateFromIntegral

41 , enumerateFromThenIntegral

43 -- ** Enumerating 'Integral' Types

44 , enumerateFromToIntegral

45 , enumerateFromThenToIntegral

47 -- ** Enumerating unbounded 'Integral' Types

48 , enumerateFromStepIntegral

50 -- ** Enumerating 'Fractional' Types

51 , enumerateFromFractional

52 , enumerateFromToFractional

53 , enumerateFromThenFractional

54 , enumerateFromThenToFractional

55 )

56where

58import Data.Fixed

59import Data.Int

60import Data.Ratio

61import Data.Word

62import Numeric.Natural

63import Data.Functor.Identity (Identity(..))

65import Streamly.Streams.StreamD (fromStreamD)

66import Streamly.Streams.StreamK (IsStream(..))

68import qualified Streamly.Streams.StreamD as D

69import qualified Streamly.Streams.Serial as Serial

71-------------------------------------------------------------------------------

72-- Enumeration of Integral types

73-------------------------------------------------------------------------------

74--

75-- | @enumerateFromStepIntegral from step@ generates an infinite stream whose

76-- first element is @from@ and the successive elements are in increments of

77-- @step@.

78--

79-- CAUTION: This function is not safe for finite integral types. It does not

80-- check for overflow, underflow or bounds.

81--

82-- @

83-- > S.toList $ S.take 4 $ S.enumerateFromStepIntegral 0 2

84-- [0,2,4,6]

85-- > S.toList $ S.take 3 $ S.enumerateFromStepIntegral 0 (-2)

86-- [0,-2,-4]

87-- @

88--

89-- @since 0.6.0

90{-# INLINE enumerateFromStepIntegral #-}

91enumerateFromStepIntegral

92 :: (IsStream t, Monad m, Integral a)

93 => a -> a -> t m a

94enumerateFromStepIntegral from stride =

95 fromStreamD $ D.enumerateFromStepIntegral from stride

97-- | Enumerate an 'Integral' type. @enumerateFromIntegral from@ generates a

98-- stream whose first element is @from@ and the successive elements are in

99-- increments of @1@. The stream is bounded by the size of the 'Integral' type.

100--

101-- @

102-- > S.toList $ S.take 4 $ S.enumerateFromIntegral (0 :: Int)

103-- [0,1,2,3]

104-- @

105--

106-- @since 0.6.0

107{-# INLINE enumerateFromIntegral #-}

108enumerateFromIntegral

109 :: (IsStream t, Monad m, Integral a, Bounded a)

110 => a -> t m a

111enumerateFromIntegral from = fromStreamD $ D.enumerateFromIntegral from

112

113-- | Enumerate an 'Integral' type in steps. @enumerateFromThenIntegral from

114-- then@ generates a stream whose first element is @from@, the second element

115-- is @then@ and the successive elements are in increments of @then - from@.

116-- The stream is bounded by the size of the 'Integral' type.

117--

118-- @

119-- > S.toList $ S.take 4 $ S.enumerateFromThenIntegral (0 :: Int) 2

120-- [0,2,4,6]

121-- > S.toList $ S.take 4 $ S.enumerateFromThenIntegral (0 :: Int) (-2)

122-- [0,-2,-4,-6]

123-- @

124--

125-- @since 0.6.0

126{-# INLINE enumerateFromThenIntegral #-}

127enumerateFromThenIntegral

128 :: (IsStream t, Monad m, Integral a, Bounded a)

129 => a -> a -> t m a

130enumerateFromThenIntegral from next =

131 fromStreamD $ D.enumerateFromThenIntegral from next

132

133-- | Enumerate an 'Integral' type up to a given limit.

134-- @enumerateFromToIntegral from to@ generates a finite stream whose first

135-- element is @from@ and successive elements are in increments of @1@ up to

136-- @to@.

137--

138-- @

139-- > S.toList $ S.enumerateFromToIntegral 0 4

140-- [0,1,2,3,4]

141-- @

142--

143-- @since 0.6.0

144{-# INLINE enumerateFromToIntegral #-}

145enumerateFromToIntegral :: (IsStream t, Monad m, Integral a) => a -> a -> t m a

146enumerateFromToIntegral from to =

147 fromStreamD $ D.enumerateFromToIntegral from to

148

149-- | Enumerate an 'Integral' type in steps up to a given limit.

150-- @enumerateFromThenToIntegral from then to@ generates a finite stream whose

151-- first element is @from@, the second element is @then@ and the successive

152-- elements are in increments of @then - from@ up to @to@.

153--

154-- @

155-- > S.toList $ S.enumerateFromThenToIntegral 0 2 6

156-- [0,2,4,6]

157-- > S.toList $ S.enumerateFromThenToIntegral 0 (-2) (-6)

158-- [0,-2,-4,-6]

159-- @

160--

161-- @since 0.6.0

162{-# INLINE enumerateFromThenToIntegral #-}

163enumerateFromThenToIntegral

164 :: (IsStream t, Monad m, Integral a)

165 => a -> a -> a -> t m a

166enumerateFromThenToIntegral from next to =

167 fromStreamD $ D.enumerateFromThenToIntegral from next to

168

169-------------------------------------------------------------------------------

170-- Enumeration of Fractional types

171-------------------------------------------------------------------------------

172--

173-- Even though the underlying implementation of enumerateFromFractional and

174-- enumerateFromThenFractional works for any 'Num' we have restricted these to

175-- 'Fractional' because these do not perform any bounds check, in contrast to

176-- integral versions and are therefore not equivalent substitutes for those.

177--

178-- | Numerically stable enumeration from a 'Fractional' number in steps of size

179-- @1@. @enumerateFromFractional from@ generates a stream whose first element

180-- is @from@ and the successive elements are in increments of @1@. No overflow

181-- or underflow checks are performed.

182--

183-- This is the equivalent to 'enumFrom' for 'Fractional' types. For example:

184--

185-- @

186-- > S.toList $ S.take 4 $ S.enumerateFromFractional 1.1

187-- [1.1,2.1,3.1,4.1]

188-- @

189--

190--

191-- @since 0.6.0

192{-# INLINE enumerateFromFractional #-}

193enumerateFromFractional :: (IsStream t, Monad m, Fractional a) => a -> t m a

194enumerateFromFractional from = fromStreamD $ D.numFrom from

195

196-- | Numerically stable enumeration from a 'Fractional' number in steps.

197-- @enumerateFromThenFractional from then@ generates a stream whose first

198-- element is @from@, the second element is @then@ and the successive elements

199-- are in increments of @then - from@. No overflow or underflow checks are

200-- performed.

201--

202-- This is the equivalent of 'enumFromThen' for 'Fractional' types. For

203-- example:

204--

205-- @

206-- > S.toList $ S.take 4 $ S.enumerateFromThenFractional 1.1 2.1

207-- [1.1,2.1,3.1,4.1]

208-- > S.toList $ S.take 4 $ S.enumerateFromThenFractional 1.1 (-2.1)

209-- [1.1,-2.1,-5.300000000000001,-8.500000000000002]

210-- @

211--

212-- @since 0.6.0

213{-# INLINE enumerateFromThenFractional #-}

214enumerateFromThenFractional

215 :: (IsStream t, Monad m, Fractional a)

216 => a -> a -> t m a

217enumerateFromThenFractional from next = fromStreamD $ D.numFromThen from next

218

219-- | Numerically stable enumeration from a 'Fractional' number to a given

220-- limit. @enumerateFromToFractional from to@ generates a finite stream whose

221-- first element is @from@ and successive elements are in increments of @1@ up

222-- to @to@.

223--

224-- This is the equivalent of 'enumFromTo' for 'Fractional' types. For

225-- example:

226--

227-- @

228-- > S.toList $ S.enumerateFromToFractional 1.1 4

229-- [1.1,2.1,3.1,4.1]

230-- > S.toList $ S.enumerateFromToFractional 1.1 4.6

231-- [1.1,2.1,3.1,4.1,5.1]

232-- @

233--

234-- Notice that the last element is equal to the specified @to@ value after

235-- rounding to the nearest integer.

236--

237-- @since 0.6.0

238{-# INLINE enumerateFromToFractional #-}

239enumerateFromToFractional

240 :: (IsStream t, Monad m, Fractional a, Ord a)

241 => a -> a -> t m a

242enumerateFromToFractional from to =

243 fromStreamD $ D.enumerateFromToFractional from to

244

245-- | Numerically stable enumeration from a 'Fractional' number in steps up to a

246-- given limit. @enumerateFromThenToFractional from then to@ generates a

247-- finite stream whose first element is @from@, the second element is @then@

248-- and the successive elements are in increments of @then - from@ up to @to@.

249--

250-- This is the equivalent of 'enumFromThenTo' for 'Fractional' types. For

251-- example:

252--

253-- @

254-- > S.toList $ S.enumerateFromThenToFractional 0.1 2 6

255-- [0.1,2.0,3.9,5.799999999999999]

256-- > S.toList $ S.enumerateFromThenToFractional 0.1 (-2) (-6)

257-- [0.1,-2.0,-4.1000000000000005,-6.200000000000001]

258-- @

259--

260--

261-- @since 0.6.0

262{-# INLINE enumerateFromThenToFractional #-}

263enumerateFromThenToFractional

264 :: (IsStream t, Monad m, Fractional a, Ord a)

265 => a -> a -> a -> t m a

266enumerateFromThenToFractional from next to =

267 fromStreamD $ D.enumerateFromThenToFractional from next to

268

269-------------------------------------------------------------------------------

270-- Enumeration of Enum types not larger than Int

271-------------------------------------------------------------------------------

272--

273-- | 'enumerateFromTo' for 'Enum' types not larger than 'Int'.

274--

275-- @since 0.6.0

276{-# INLINE enumerateFromToSmall #-}

277enumerateFromToSmall :: (IsStream t, Monad m, Enum a) => a -> a -> t m a

278enumerateFromToSmall from to = Serial.map toEnum $

279 enumerateFromToIntegral (fromEnum from) (fromEnum to)

280

281-- | 'enumerateFromThenTo' for 'Enum' types not larger than 'Int'.

282--

283-- @since 0.6.0

284{-# INLINE enumerateFromThenToSmall #-}

285enumerateFromThenToSmall :: (IsStream t, Monad m, Enum a)

286 => a -> a -> a -> t m a

287enumerateFromThenToSmall from next to = Serial.map toEnum $

288 enumerateFromThenToIntegral (fromEnum from) (fromEnum next) (fromEnum to)

289

290-- | 'enumerateFromThen' for 'Enum' types not larger than 'Int'.

291--

292-- Note: We convert the 'Enum' to 'Int' and enumerate the 'Int'. If a

293-- type is bounded but does not have a 'Bounded' instance then we can go on

294-- enumerating it beyond the legal values of the type, resulting in the failure

295-- of 'toEnum' when converting back to 'Enum'. Therefore we require a 'Bounded'

296-- instance for this function to be safely used.

297--

298-- @since 0.6.0

299{-# INLINE enumerateFromThenSmallBounded #-}

300enumerateFromThenSmallBounded :: (IsStream t, Monad m, Enumerable a, Bounded a)

301 => a -> a -> t m a

302enumerateFromThenSmallBounded from next =

303 case fromEnum next >= fromEnum from of

304 True -> enumerateFromThenTo from next maxBound

305 False -> enumerateFromThenTo from next minBound

306

307-------------------------------------------------------------------------------

308-- Enumerable type class

309-------------------------------------------------------------------------------

310--

311-- NOTE: We would like to rewrite calls to fromList [1..] etc. to stream

312-- enumerations like this:

313--

314-- {-# RULES "fromList enumFrom" [1]

315-- forall (a :: Int). D.fromList (enumFrom a) = D.enumerateFromIntegral a #-}

316--

317-- But this does not work because enumFrom is a class method and GHC rewrites

318-- it quickly, so we do not get a chance to have our rule fired.

319

320-- | Types that can be enumerated as a stream. The operations in this type

321-- class are equivalent to those in the 'Enum' type class, except that these

322-- generate a stream instead of a list. Use the functions in

323-- "Streamly.Enumeration" module to define new instances.

324--

325-- @since 0.6.0

326class Enum a => Enumerable a where

327 -- | @enumerateFrom from@ generates a stream starting with the element

328 -- @from@, enumerating up to 'maxBound' when the type is 'Bounded' or

329 -- generating an infinite stream when the type is not 'Bounded'.

330 --

331 -- @

332 -- > S.toList $ S.take 4 $ S.enumerateFrom (0 :: Int)

333 -- [0,1,2,3]

334 -- @

335 --

336 -- For 'Fractional' types, enumeration is numerically stable. However, no

337 -- overflow or underflow checks are performed.

338 --

339 -- @

340 -- > S.toList $ S.take 4 $ S.enumerateFrom 1.1

341 -- [1.1,2.1,3.1,4.1]

342 -- @

343 --

344 -- @since 0.6.0

345 enumerateFrom :: (IsStream t, Monad m) => a -> t m a

346

347 -- | Generate a finite stream starting with the element @from@, enumerating

348 -- the type up to the value @to@. If @to@ is smaller than @from@ then an

349 -- empty stream is returned.

350 --

351 -- @

352 -- > S.toList $ S.enumerateFromTo 0 4

353 -- [0,1,2,3,4]

354 -- @

355 --

356 -- For 'Fractional' types, the last element is equal to the specified @to@

357 -- value after rounding to the nearest integral value.

358 --

359 -- @

360 -- > S.toList $ S.enumerateFromTo 1.1 4

361 -- [1.1,2.1,3.1,4.1]

362 -- > S.toList $ S.enumerateFromTo 1.1 4.6

363 -- [1.1,2.1,3.1,4.1,5.1]

364 -- @

365 --

366 -- @since 0.6.0

367 enumerateFromTo :: (IsStream t, Monad m) => a -> a -> t m a

368

369 -- | @enumerateFromThen from then@ generates a stream whose first element

370 -- is @from@, the second element is @then@ and the successive elements are

371 -- in increments of @then - from@. Enumeration can occur downwards or

372 -- upwards depending on whether @then@ comes before or after @from@. For

373 -- 'Bounded' types the stream ends when 'maxBound' is reached, for

374 -- unbounded types it keeps enumerating infinitely.

375 --

376 -- @

377 -- > S.toList $ S.take 4 $ S.enumerateFromThen 0 2

378 -- [0,2,4,6]

379 -- > S.toList $ S.take 4 $ S.enumerateFromThen 0 (-2)

380 -- [0,-2,-4,-6]

381 -- @

382 --

383 -- @since 0.6.0

384 enumerateFromThen :: (IsStream t, Monad m) => a -> a -> t m a

385

386 -- | @enumerateFromThenTo from then to@ generates a finite stream whose

387 -- first element is @from@, the second element is @then@ and the successive

388 -- elements are in increments of @then - from@ up to @to@. Enumeration can

389 -- occur downwards or upwards depending on whether @then@ comes before or

390 -- after @from@.

391 --

392 -- @

393 -- > S.toList $ S.enumerateFromThenTo 0 2 6

394 -- [0,2,4,6]

395 -- > S.toList $ S.enumerateFromThenTo 0 (-2) (-6)

396 -- [0,-2,-4,-6]

397 -- @

398 --

399 -- @since 0.6.0

400 enumerateFromThenTo :: (IsStream t, Monad m) => a -> a -> a -> t m a

401

402-- MAYBE: Sometimes it is more convenient to know the count rather then the

403-- ending or starting element. For those cases we can define the folllowing

404-- APIs. All of these will work only for bounded types if we represent the

405-- count by Int.

406--

407-- enumerateN

408-- enumerateFromN

409-- enumerateToN

410-- enumerateFromStep

411-- enumerateFromStepN

412

413-------------------------------------------------------------------------------

414-- Convenient functions for bounded types

415-------------------------------------------------------------------------------

416--

417-- |

418-- > enumerate = enumerateFrom minBound

419--

420-- Enumerate a 'Bounded' type from its 'minBound' to 'maxBound'

421--

422-- @since 0.6.0

423{-# INLINE enumerate #-}

424enumerate :: (IsStream t, Monad m, Bounded a, Enumerable a) => t m a

425enumerate = enumerateFrom minBound

426

427-- |

428-- > enumerateTo = enumerateFromTo minBound

429--

430-- Enumerate a 'Bounded' type from its 'minBound' to specified value.

431--

432-- @since 0.6.0

433{-# INLINE enumerateTo #-}

434enumerateTo :: (IsStream t, Monad m, Bounded a, Enumerable a) => a -> t m a

435enumerateTo = enumerateFromTo minBound

436

437-- |

438-- > enumerateFromBounded = enumerateFromTo from maxBound

439--

440-- 'enumerateFrom' for 'Bounded' 'Enum' types.

441--

442-- @since 0.6.0

443{-# INLINE enumerateFromBounded #-}

444enumerateFromBounded :: (IsStream t, Monad m, Enumerable a, Bounded a)

445 => a -> t m a

446enumerateFromBounded from = enumerateFromTo from maxBound

447

448-------------------------------------------------------------------------------

449-- Enumerable Instances

450-------------------------------------------------------------------------------

451--

452-- For Enum types smaller than or equal to Int size.

453#define ENUMERABLE_BOUNDED_SMALL(SMALL_TYPE) \

454instance Enumerable SMALL_TYPE where { \

455 {-# INLINE enumerateFrom #-}; \

456 enumerateFrom = enumerateFromBounded; \

457 {-# INLINE enumerateFromThen #-}; \

458 enumerateFromThen = enumerateFromThenSmallBounded; \

459 {-# INLINE enumerateFromTo #-}; \

460 enumerateFromTo = enumerateFromToSmall; \

461 {-# INLINE enumerateFromThenTo #-}; \

462 enumerateFromThenTo = enumerateFromThenToSmall }

463

464

465ENUMERABLE_BOUNDED_SMALL(())

466ENUMERABLE_BOUNDED_SMALL(Bool)

467ENUMERABLE_BOUNDED_SMALL(Ordering)

468ENUMERABLE_BOUNDED_SMALL(Char)

469

470-- For bounded Integral Enum types, may be larger than Int.

471#define ENUMERABLE_BOUNDED_INTEGRAL(INTEGRAL_TYPE) \

472instance Enumerable INTEGRAL_TYPE where { \

473 {-# INLINE enumerateFrom #-}; \

474 enumerateFrom = enumerateFromIntegral; \

475 {-# INLINE enumerateFromThen #-}; \

476 enumerateFromThen = enumerateFromThenIntegral; \

477 {-# INLINE enumerateFromTo #-}; \

478 enumerateFromTo = enumerateFromToIntegral; \

479 {-# INLINE enumerateFromThenTo #-}; \

480 enumerateFromThenTo = enumerateFromThenToIntegral }

481

482ENUMERABLE_BOUNDED_INTEGRAL(Int)

483ENUMERABLE_BOUNDED_INTEGRAL(Int8)

484ENUMERABLE_BOUNDED_INTEGRAL(Int16)

485ENUMERABLE_BOUNDED_INTEGRAL(Int32)

486ENUMERABLE_BOUNDED_INTEGRAL(Int64)

487ENUMERABLE_BOUNDED_INTEGRAL(Word)

488ENUMERABLE_BOUNDED_INTEGRAL(Word8)

489ENUMERABLE_BOUNDED_INTEGRAL(Word16)

490ENUMERABLE_BOUNDED_INTEGRAL(Word32)

491ENUMERABLE_BOUNDED_INTEGRAL(Word64)

492

493-- For unbounded Integral Enum types.

494#define ENUMERABLE_UNBOUNDED_INTEGRAL(INTEGRAL_TYPE) \

495instance Enumerable INTEGRAL_TYPE where { \

496 {-# INLINE enumerateFrom #-}; \

497 enumerateFrom from = enumerateFromStepIntegral from 1; \

498 {-# INLINE enumerateFromThen #-}; \

499 enumerateFromThen from next = \

500 enumerateFromStepIntegral from (next - from); \

501 {-# INLINE enumerateFromTo #-}; \

502 enumerateFromTo = enumerateFromToIntegral; \

503 {-# INLINE enumerateFromThenTo #-}; \

504 enumerateFromThenTo = enumerateFromThenToIntegral }

505

506ENUMERABLE_UNBOUNDED_INTEGRAL(Integer)

507ENUMERABLE_UNBOUNDED_INTEGRAL(Natural)

508

509#define ENUMERABLE_FRACTIONAL(FRACTIONAL_TYPE,CONSTRAINT) \

510instance (CONSTRAINT) => Enumerable (FRACTIONAL_TYPE) where { \

511 {-# INLINE enumerateFrom #-}; \

512 enumerateFrom = enumerateFromFractional; \

513 {-# INLINE enumerateFromThen #-}; \

514 enumerateFromThen = enumerateFromThenFractional; \

515 {-# INLINE enumerateFromTo #-}; \

516 enumerateFromTo = enumerateFromToFractional; \

517 {-# INLINE enumerateFromThenTo #-}; \

518 enumerateFromThenTo = enumerateFromThenToFractional }

519

520ENUMERABLE_FRACTIONAL(Float,)

521ENUMERABLE_FRACTIONAL(Double,)

522ENUMERABLE_FRACTIONAL(Fixed a,HasResolution a)

523ENUMERABLE_FRACTIONAL(Ratio a,Integral a)

524

525#if __GLASGOW_HASKELL__ >= 800

526instance Enumerable a => Enumerable (Identity a) where

527 {-# INLINE enumerateFrom #-}

528 enumerateFrom (Identity from) = Serial.map Identity $

529 enumerateFrom from

530 {-# INLINE enumerateFromThen #-}

531 enumerateFromThen (Identity from) (Identity next) = Serial.map Identity $

532 enumerateFromThen from next

533 {-# INLINE enumerateFromTo #-}

534 enumerateFromTo (Identity from) (Identity to) = Serial.map Identity $

535 enumerateFromTo from to

536 {-# INLINE enumerateFromThenTo #-}

537 enumerateFromThenTo (Identity from) (Identity next) (Identity to) =

538 Serial.map Identity $ enumerateFromThenTo from next to

539#endif

540

541-- TODO

542{-

543instance Enumerable a => Enumerable (Last a)

544instance Enumerable a => Enumerable (First a)

545instance Enumerable a => Enumerable (Max a)

546instance Enumerable a => Enumerable (Min a)

547instance Enumerable a => Enumerable (Const a b)

548instance Enumerable (f a) => Enumerable (Alt f a)

549instance Enumerable (f a) => Enumerable (Ap f a)

550-}