module Data.Blockchain.Crypto.HashTree
( HashTreeRoot
, unHashTreeRoot
, hashTreeRoot
) where
import qualified Data.Aeson as Aeson
import Data.Blockchain.Crypto.Hash
newtype HashTreeRoot a = HashTreeRoot { unHashTreeRoot :: Hash a }
deriving (Aeson.FromJSON, Aeson.ToJSON, Eq, Ord, Show)
hashTreeRoot :: forall a. ToHash a => [a] -> HashTreeRoot a
hashTreeRoot = HashTreeRoot . buildHash
where
buildHash :: [a] -> Hash a
buildHash [] = mempty
buildHash [x] = hash x
buildHash xs = mappend (buildHash left) (buildHash right)
where
(left, right) = splitAt i xs
i = until (\x -> x * 2 >= length xs) (*2) 1