Last active
February 26, 2022 22:48
-
-
Save pete-murphy/8f54913def8c57263f45e2af4cf44c1b to your computer and use it in GitHub Desktop.
FingerTree usage
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| module Main where | |
| import Prelude | |
| import Data.Array as Array | |
| import Data.FingerTree (FingerTree) | |
| import Data.FingerTree as FingerTree | |
| import Data.Lazy as Lazy | |
| import Data.Monoid.Additive (Additive(..)) | |
| import Data.Newtype (class Newtype) | |
| import Data.Sequence.Internal (class Measured) | |
| import Data.Traversable as Traversable | |
| import Data.Tuple (Tuple(..)) | |
| import Effect (Effect) | |
| import Effect.Class.Console as Console | |
| import Partial.Unsafe as Unsafe | |
| import Safe.Coerce as Coerce | |
| arrayA :: Array Int | |
| arrayA = [ 9, 5, 4, 7 ] | |
| arrayB :: Array Int | |
| arrayB = [ 3, 2, 4, 5, 2, 1, 1, 3, 4 ] | |
| computeSolution | |
| :: Array Int -- Array of target numbers we must sum to | |
| -> Array Int -- Array of input numbers being summed | |
| -> Array (Array Int) | |
| computeSolution sumArray valueArray = | |
| let | |
| valueFingerTree :: FingerTree (Additive Int) (Additive' Int) | |
| valueFingerTree = FingerTree.toFingerTree (map Coerce.coerce valueArray) | |
| finalState = | |
| Traversable.mapAccumL computation valueFingerTree (map Additive sumArray) | |
| computation inputs target = | |
| let | |
| Tuple result_ nextInputs = | |
| Unsafe.unsafePartial FingerTree.split (_ > target) inputs | |
| result = map Coerce.coerce (Array.fromFoldable (Lazy.force result_)) | |
| in | |
| { accum: Lazy.force nextInputs, value: result } | |
| in | |
| finalState.value | |
| -- | Newtype to workaround orphan instances | |
| newtype Additive' a = Additive' (Additive a) | |
| derive instance Newtype (Additive' a) _ | |
| derive newtype instance Semiring a => Semigroup (Additive' a) | |
| derive newtype instance Semiring a => Monoid (Additive' a) | |
| instance Measured (Additive' Int) (Additive Int) where | |
| measure (Additive' m) = m | |
| main :: Effect Unit | |
| main = do | |
| Console.logShow (computeSolution arrayA arrayB) | |
| -- [[3,2,4],[5],[2,1,1],[3,4]] | |
| let | |
| largeArrayA = Array.concat (Array.replicate 10_000 arrayA) | |
| largeArrayB = Array.concat (Array.replicate 10_000 arrayB) | |
| Console.time "Large" | |
| Console.logShow (computeSolution largeArrayA largeArrayB) | |
| Console.timeEnd "Large" |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| -- You can extend the official package set, adding `sequences`: | |
| let upstream = | |
| https://github.com/purescript/package-sets/releases/download/psc-0.14.5-20220224/packages.dhall sha256:67cc3d4f0e8fb72bb1413ba94ddd72a3ceb0783eb725e3b22ad7568b3b581163 | |
| let additions = | |
| { sequences = | |
| { dependencies = [] : List Text | |
| , repo = "https://github.com/hdgarrood/purescript-sequences" | |
| , version = "v3.0.2" | |
| } | |
| } | |
| in upstream // additions | |
| -- and then add to `spago.dhall` (or just `spago install sequences` after adding | |
| -- it here) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment