chimera-0.4.1.0: Lazy infinite streams with O(1) indexing and applications for memoization

Copyright | (c) 2017 Andrew Lelechenko
License | BSD3
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | None
Language | Haskell2010

Data.Chimera.ContinuousMapping

Description

Helpers for continuous mappings, useful to memoize functions on `Int` (instead of `Word` only) and functions over two and three arguments.

Example 1

Imagine writing a program to simulate Rule 90. This is a cellular automaton, which consists of an infinite one-dimensional line of cells, each being either dead (`False`) or alive (`True`). If two neighbours of a cell are equal, it becomes dead on the next step, otherwise alive.

Usually cellular automata are modelled by a finite vector. This is a bit suboptimal, because cellular automata may grow in different directions over time, but with a finite vector one has to define a bounding segment well beforehand. Moreover, what if we are interested to explore an evolution of an essentially infinite initial configuration?

It would be natural to encode an initial configuration as a function `Int` `->` `Bool`, which takes a coordinate and returns the status of the corresponding cell. Define a function, which translates the automaton to the next step:

    step :: (Int -> Bool) -> (Int -> Bool)
    step current = \n -> current (n - 1) /= current (n + 1)

Unfortunately, iterating `step` would be extremely slow because of branching recursion. One could suggest to introduce a caching layer:

    step :: (Int -> Bool) -> (Int -> Bool)
    step current = \n -> current' (n - 1) /= current' (n + 1)
      where
        current' = memoize (current . fromIntegral) . fromIntegral

Unfortunately, it would not work well, because `fromIntegral` `::` `Int` `->` `Word` maps `-1` to `maxBound` and it would take ages to memoize everything up to `maxBound`. But continuous mappings `intToWord` and `wordToInt` avoid this issue:

    step :: (Int -> Bool) -> (Int -> Bool)
    step current = \n -> current' (n - 1) /= current' (n + 1)
      where
        current' = memoize (current . wordToInt) . intToWord

Example 2

What about another famous cellular automaton: Conway's Game of Life? It is two-dimensional, so its state can be represented as a function `Int` `->` `Int` `->` `Bool`. Following the approach above, we would like to memoize such functions. Namely, cast the state to `Word` `->` `Bool`, ready for memoization:

    cast :: (Int -> Int -> Bool) -> (Word -> Bool)
    cast f = \n -> let (x, y) = fromZCurve n in f (fromHalf x) (fromHalf y)
      where
        fromHalf :: HalfWord -> Int
        fromHalf = wordToInt . fromIntegral @HalfWord @Word

and then back:

    uncast :: (Word -> Bool) -> (Int -> Int -> Bool)
    uncast g = \x y -> g (toZCurve (toHalf x) (toHalf y))
      where
        toHalf :: Int -> HalfWord
        toHalf = fromIntegral @Word @HalfWord . intToWord

Synopsis

- intToWord :: Int -> Word
- wordToInt :: Word -> Int
- data HalfWord
- toZCurve :: HalfWord -> HalfWord -> Word
- fromZCurve :: Word -> (HalfWord, HalfWord)
- throughZCurveFix :: ((HalfWord -> HalfWord -> a) -> HalfWord -> HalfWord -> a) -> (Word -> a) -> Word -> a
- data ThirdWord
- toZCurve3 :: ThirdWord -> ThirdWord -> ThirdWord -> Word
- fromZCurve3 :: Word -> (ThirdWord, ThirdWord, ThirdWord)
- throughZCurveFix3 :: ((ThirdWord -> ThirdWord -> ThirdWord -> a) -> ThirdWord -> ThirdWord -> ThirdWord -> a) -> (Word -> a) -> Word -> a

# Documentation

intToWord :: Int -> Word Source #

Total map, which satisfies

    abs (intToWord x - intToWord y) <= 2 * abs (x - y)

Note that usual `fromIntegral` `::` `Int` `->` `Word` does not satisfy this inequality, because it has a discontinuity between −1 and 0.

    >>> map intToWord [-5..5]
    [9,7,5,3,1,0,2,4,6,8,10]

Since: 0.2.0.0

wordToInt :: Word -> Int Source #

Inverse for `intToWord`.

    >>> map wordToInt [0..10]
    [0,-1,1,-2,2,-3,3,-4,4,-5,5]

Since: 0.2.0.0

data HalfWord Source #

32 bits on 64-bit architecture, 16 bits on 32-bit architecture.

To create a value of type `HalfWord` use `fromIntegral`.

Since: 0.4.0.0

#### Instances

Instances details

Bits HalfWord Source # |

Instance details

Defined in Data.Chimera.ContinuousMapping

Methods

(.&.) :: HalfWord -> HalfWord -> HalfWord Source #

(.|.) :: HalfWord -> HalfWord -> HalfWord Source #

xor :: HalfWord -> HalfWord -> HalfWord Source #

complement :: HalfWord -> HalfWord Source #

shift :: HalfWord -> Int -> HalfWord Source #

rotate :: HalfWord -> Int -> HalfWord Source #

zeroBits :: HalfWord Source #

bit :: Int -> HalfWord Source #

setBit :: HalfWord -> Int -> HalfWord Source #

clearBit :: HalfWord -> Int -> HalfWord Source #

complementBit :: HalfWord -> Int -> HalfWord Source #

testBit :: HalfWord -> Int -> Bool Source #

bitSizeMaybe :: HalfWord -> Maybe Int Source #

bitSize :: HalfWord -> Int Source #

isSigned :: HalfWord -> Bool Source #

shiftL :: HalfWord -> Int -> HalfWord Source #

unsafeShiftL :: HalfWord -> Int -> HalfWord Source #

shiftR :: HalfWord -> Int -> HalfWord Source #

unsafeShiftR :: HalfWord -> Int -> HalfWord Source #

rotateL :: HalfWord -> Int -> HalfWord Source #

rotateR :: HalfWord -> Int -> HalfWord Source #

popCount :: HalfWord -> Int Source #

FiniteBits HalfWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods finiteBitSize :: HalfWord -> Int Source # countLeadingZeros :: HalfWord -> Int Source # countTrailingZeros :: HalfWord -> Int Source #
Bounded HalfWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods minBound :: HalfWord Source # maxBound :: HalfWord Source #
Enum HalfWord Source # |

Instance details

Defined in Data.Chimera.ContinuousMapping

Methods

succ :: HalfWord -> HalfWord Source #

pred :: HalfWord -> HalfWord Source #

toEnum :: Int -> HalfWord Source #

fromEnum :: HalfWord -> Int Source #

enumFrom :: HalfWord -> [HalfWord] Source #

enumFromThen :: HalfWord -> HalfWord -> [HalfWord] Source #

enumFromTo :: HalfWord -> HalfWord -> [HalfWord] Source #

enumFromThenTo :: HalfWord -> HalfWord -> HalfWord -> [HalfWord] Source #

Num HalfWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods (+) :: HalfWord -> HalfWord -> HalfWord Source # (-) :: HalfWord -> HalfWord -> HalfWord Source # (*) :: HalfWord -> HalfWord -> HalfWord Source # negate :: HalfWord -> HalfWord Source # abs :: HalfWord -> HalfWord Source # signum :: HalfWord -> HalfWord Source # fromInteger :: Integer -> HalfWord Source #
Read HalfWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods readsPrec :: Int -> ReadS HalfWord Source # readList :: ReadS [HalfWord] Source # readPrec :: ReadPrec HalfWord Source # readListPrec :: ReadPrec [HalfWord] Source #
Integral HalfWord Source # |

Instance details

Defined in Data.Chimera.ContinuousMapping

Methods

quot :: HalfWord -> HalfWord -> HalfWord Source #

rem :: HalfWord -> HalfWord -> HalfWord Source #

div :: HalfWord -> HalfWord -> HalfWord Source #

mod :: HalfWord -> HalfWord -> HalfWord Source #

quotRem :: HalfWord -> HalfWord -> (HalfWord, HalfWord) Source #

divMod :: HalfWord -> HalfWord -> (HalfWord, HalfWord) Source #

toInteger :: HalfWord -> Integer Source #

Real HalfWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods toRational :: HalfWord -> Rational Source #
Show HalfWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods showsPrec :: Int -> HalfWord -> ShowS Source # show :: HalfWord -> String Source # showList :: [HalfWord] -> ShowS Source #
Eq HalfWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods (==) :: HalfWord -> HalfWord -> Bool Source # (/=) :: HalfWord -> HalfWord -> Bool Source #
Ord HalfWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods compare :: HalfWord -> HalfWord -> Ordering Source # (<) :: HalfWord -> HalfWord -> Bool Source # (<=) :: HalfWord -> HalfWord -> Bool Source # (>) :: HalfWord -> HalfWord -> Bool Source # (>=) :: HalfWord -> HalfWord -> Bool Source # max :: HalfWord -> HalfWord -> HalfWord Source # min :: HalfWord -> HalfWord -> HalfWord Source #

toZCurve :: HalfWord -> HalfWord -> Word Source #

Total map from plain to line, continuous almost everywhere. See Z-order curve.

    >>> [ toZCurve x y | x <- [0..3], y <- [0..3] ]
    [0,2,8,10,1,3,9,11,4,6,12,14,5,7,13,15]

Since: 0.2.0.0

fromZCurve :: Word -> (HalfWord, HalfWord) Source #

Inverse for `toZCurve`. See Z-order curve.

    >>> map fromZCurve [0..15]
    [(0,0),(1,0),(0,1),(1,1),(2,0),(3,0),(2,1),(3,1),(0,2),(1,2),(0,3),(1,3),(2,2),(3,2),(2,3),(3,3)]

Since: 0.2.0.0

throughZCurveFix :: ((HalfWord -> HalfWord -> a) -> HalfWord -> HalfWord -> a) -> (Word -> a) -> Word -> a Source #

For an input function `f` return function `g` such that `fix` `f` = (`fix` `g` `.`) `.` `toZCurve`.

Since: 0.4.0.0

data ThirdWord Source #

21 bits on 64-bit architecture, 10 bits on 32-bit architecture.

To create a value of type `ThirdWord` use `fromIntegral`.

Since: 0.4.0.0

#### Instances

Instances details

Bits ThirdWord Source # |

Instance details

Defined in Data.Chimera.ContinuousMapping

Methods

(.&.) :: ThirdWord -> ThirdWord -> ThirdWord Source #

(.|.) :: ThirdWord -> ThirdWord -> ThirdWord Source #

xor :: ThirdWord -> ThirdWord -> ThirdWord Source #

complement :: ThirdWord -> ThirdWord Source #

shift :: ThirdWord -> Int -> ThirdWord Source #

rotate :: ThirdWord -> Int -> ThirdWord Source #

zeroBits :: ThirdWord Source #

bit :: Int -> ThirdWord Source #

setBit :: ThirdWord -> Int -> ThirdWord Source #

clearBit :: ThirdWord -> Int -> ThirdWord Source #

complementBit :: ThirdWord -> Int -> ThirdWord Source #

testBit :: ThirdWord -> Int -> Bool Source #

bitSizeMaybe :: ThirdWord -> Maybe Int Source #

bitSize :: ThirdWord -> Int Source #

isSigned :: ThirdWord -> Bool Source #

shiftL :: ThirdWord -> Int -> ThirdWord Source #

unsafeShiftL :: ThirdWord -> Int -> ThirdWord Source #

shiftR :: ThirdWord -> Int -> ThirdWord Source #

unsafeShiftR :: ThirdWord -> Int -> ThirdWord Source #

rotateL :: ThirdWord -> Int -> ThirdWord Source #

rotateR :: ThirdWord -> Int -> ThirdWord Source #

popCount :: ThirdWord -> Int Source #

FiniteBits ThirdWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods finiteBitSize :: ThirdWord -> Int Source # countLeadingZeros :: ThirdWord -> Int Source # countTrailingZeros :: ThirdWord -> Int Source #
Bounded ThirdWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods minBound :: ThirdWord Source # maxBound :: ThirdWord Source #
Enum ThirdWord Source # |

Instance details

Defined in Data.Chimera.ContinuousMapping

Methods

succ :: ThirdWord -> ThirdWord Source #

pred :: ThirdWord -> ThirdWord Source #

toEnum :: Int -> ThirdWord Source #

fromEnum :: ThirdWord -> Int Source #

enumFrom :: ThirdWord -> [ThirdWord] Source #

enumFromThen :: ThirdWord -> ThirdWord -> [ThirdWord] Source #

enumFromTo :: ThirdWord -> ThirdWord -> [ThirdWord] Source #

enumFromThenTo :: ThirdWord -> ThirdWord -> ThirdWord -> [ThirdWord] Source #

Num ThirdWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods (+) :: ThirdWord -> ThirdWord -> ThirdWord Source # (-) :: ThirdWord -> ThirdWord -> ThirdWord Source # (*) :: ThirdWord -> ThirdWord -> ThirdWord Source # negate :: ThirdWord -> ThirdWord Source # abs :: ThirdWord -> ThirdWord Source # signum :: ThirdWord -> ThirdWord Source # fromInteger :: Integer -> ThirdWord Source #
Read ThirdWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods readsPrec :: Int -> ReadS ThirdWord Source # readList :: ReadS [ThirdWord] Source # readPrec :: ReadPrec ThirdWord Source # readListPrec :: ReadPrec [ThirdWord] Source #
Integral ThirdWord Source # |

Instance details

Defined in Data.Chimera.ContinuousMapping

Methods

quot :: ThirdWord -> ThirdWord -> ThirdWord Source #

rem :: ThirdWord -> ThirdWord -> ThirdWord Source #

div :: ThirdWord -> ThirdWord -> ThirdWord Source #

mod :: ThirdWord -> ThirdWord -> ThirdWord Source #

quotRem :: ThirdWord -> ThirdWord -> (ThirdWord, ThirdWord) Source #

divMod :: ThirdWord -> ThirdWord -> (ThirdWord, ThirdWord) Source #

toInteger :: ThirdWord -> Integer Source #

Real ThirdWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods toRational :: ThirdWord -> Rational Source #
Show ThirdWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods showsPrec :: Int -> ThirdWord -> ShowS Source # show :: ThirdWord -> String Source # showList :: [ThirdWord] -> ShowS Source #
Eq ThirdWord Source # |
Instance details Defined in Data.Chimera.ContinuousMapping Methods (==) :: ThirdWord -> ThirdWord -> Bool Source # (/=) :: ThirdWord -> ThirdWord -> Bool Source #
Ord ThirdWord Source # |

Instance details

Defined in Data.Chimera.ContinuousMapping

Methods

compare :: ThirdWord -> ThirdWord -> Ordering Source #

(<) :: ThirdWord -> ThirdWord -> Bool Source #

(<=) :: ThirdWord -> ThirdWord -> Bool Source #

(>) :: ThirdWord -> ThirdWord -> Bool Source #

(>=) :: ThirdWord -> ThirdWord -> Bool Source #

max :: ThirdWord -> ThirdWord -> ThirdWord Source #

min :: ThirdWord -> ThirdWord -> ThirdWord Source #

toZCurve3 :: ThirdWord -> ThirdWord -> ThirdWord -> Word Source #

Total map from space to line, continuous almost everywhere. See Z-order curve.

    >>> [ toZCurve3 x y z | x <- [0..3], y <- [0..3], z <- [0..3] ]
    [0,4,32,36,2,6,34,38,16,20,48,52,18,22,50,54,1,5,33,37,3,7,35,39,17,21,49,53,19,23,51,55,
    8,12,40,44,10,14,42,46,24,28,56,60,26,30,58,62,9,13,41,45,11,15,43,47,25,29,57,61,27,31,59,63]

Since: 0.2.0.0

fromZCurve3 :: Word -> (ThirdWord, ThirdWord, ThirdWord) Source #

Inverse for `toZCurve3`. See Z-order curve.

    >>> map fromZCurve3 [0..63]
    [(0,0,0),(1,0,0),(0,1,0),(1,1,0),(0,0,1),(1,0,1),(0,1,1),(1,1,1),(2,0,0),(3,0,0),(2,1,0),(3,1,0),(2,0,1),(3,0,1),(2,1,1),(3,1,1),
     (0,2,0),(1,2,0),(0,3,0),(1,3,0),(0,2,1),(1,2,1),(0,3,1),(1,3,1),(2,2,0),(3,2,0),(2,3,0),(3,3,0),(2,2,1),(3,2,1),(2,3,1),(3,3,1),
     (0,0,2),(1,0,2),(0,1,2),(1,1,2),(0,0,3),(1,0,3),(0,1,3),(1,1,3),(2,0,2),(3,0,2),(2,1,2),(3,1,2),(2,0,3),(3,0,3),(2,1,3),(3,1,3),
     (0,2,2),(1,2,2),(0,3,2),(1,3,2),(0,2,3),(1,2,3),(0,3,3),(1,3,3),(2,2,2),(3,2,2),(2,3,2),(3,3,2),(2,2,3),(3,2,3),(2,3,3),(3,3,3)]

Since: 0.2.0.0

throughZCurveFix3 :: ((ThirdWord -> ThirdWord -> ThirdWord -> a) -> ThirdWord -> ThirdWord -> ThirdWord -> a) -> (Word -> a) -> Word -> a Source #

For an input function `f` return function `g` such that `fix` `f` = ((`fix` `g` `.`) `.`) `.` `toZCurve3`.

Since: 0.4.0.0