Knuth's power tree: Difference between revisions

Line 468:

) where

import Data.Foldable (toList)

import Data.Map.Strict (Map)

import qualified Data.Map.Strict as Map

import Data.Maybe (fromMaybe)

import Data.List (foldl')

import Data.Sequence (Seq (..), (|>))

import qualified Data.Sequence as Seq

import Numeric.Natural (Natural)

type M = Map Natural ~~[Natural]~~

type M = Map Natural S

type S = Seq Natural

levels :: [M]

levels = ~~iterate~~ ~~step~~ $ Map.singleton 1 ~~[1]~~

levels = let s = Seq.singleton 1 in fst <$> iterate step (Map.singleton 1 s, s)

step :: M -> M

step :: (M, S) -> (M, S)

step m = foldl' f m $ ~~Map.keys m~~

step (m, xs) = foldl' f (m, Empty) xs

where

f :: M -> Natural -> M

f :: (M, S) -> Natural -> (M, S)

f m' n = foldl' g m' ns

f (m', ys) n = foldl' g (m', ys) ns

where

ns :: ~~[Natural]~~

ns :: S

ns = m' Map.! n

g :: M -> Natural -> M

g :: (M, S) -> Natural -> (M, S)

g m'' k =

g (m'', zs) k =

let l = n + k

in Map.~~insertWith (flip const)~~ l ~~(ns ++ [l])~~ m''

in case Map.lookup l m'' of

Nothing -> (Map.insert l (ns |> l) m'', zs |> l)

⚫

Just _ -> (m'', zs)

powerTree :: Natural -> [Natural]

Line 499:

Line 506:

go :: [M] -> [Natural]

go [] = error "impossible branch"

go (m : ms) = ~~case~~ Map.lookup n m of

go (m : ms) = fromMaybe (go ms) $ toList <$> Map.lookup n m

Nothing -> go ms

⚫

Just xs -> xs

power :: forall a. Num a => a -> Natural -> a

Line 516:

Line 521:

(The <tt>CReal</tt> type from package <tt>numbers</tt> is used to get the ''exact'' result for the last example.)

<pre>

~~<pre>~~powerTree 0 = [], power 2 0 = 1

powerTree 0 = [], power 2 0 = 1

powerTree 1 = [1], power 2 1 = 2

powerTree 2 = [1,2], power 2 2 = 4

Line 527:

Line 533:

powerTree 9 = [1,2,3,6,9], power 2 9 = 512

powerTree 10 = [1,2,3,5,10], power 2 10 = 1024

powerTree 11 = [1,2,3,6,9,11], power 2 11 = 2048

powerTree 11 = [1,2,3,5,10,11], power 2 11 = 2048

powerTree 12 = [1,2,3,6,12], power 2 12 = 4096

powerTree 13 = [1,2,3,5,10,13], power 2 13 = 8192

powerTree 14 = [1,2,3,5,7,14], power 2 14 = 16384

powerTree 15 = [1,2,3,6,9,15], power 2 15 = 32768

powerTree 15 = [1,2,3,5,10,15], power 2 15 = 32768

powerTree 16 = [1,2,4,8,16], power 2 16 = 65536

powerTree 17 = [1,2,4,8,16,17], power 2 17 = 131072

powerTree 191 = [1,2,4,8,16,17,25,29,58,87,~~174~~,191], power 3 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347

powerTree 191 = [1,2,3,5,7,14,19,38,57,95,190,191], power 3 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347

powerTree 81 = [1,2,3,6,9,18,27,54,81], power 1.1 81 = 2253.240236044012487937308538033349567966729852481170503814810577345406584190098644811

powerTree 81 = [1,2,3,5,10,20,40,41,81], power 1.1 81 = 2253.240236044012487937308538033349567966729852481170503814810577345406584190098644811

</pre>

=={{header|J}}==