ninetynine-1.3.0: Ninety-Nine Haskell Problems

Copyright	Copyright (C) 2023 Yoo Chung
License	GPL-3.0-or-later
Maintainer	dev@chungyc.org
Safe Haskell	Safe-Inferred
Language	GHC2021

Problems.MultiwayTrees

Description

Supporting definitions for multiway tree problems.

Synopsis

data MultiwayTree a = MultiwayTree a [MultiwayTree a]
multitree1 :: MultiwayTree Char
multitree2 :: MultiwayTree Char
multitree3 :: MultiwayTree Char
multitree4 :: MultiwayTree Char
multitree5 :: MultiwayTree Char
multitreeSize :: MultiwayTree a -> Int

Documentation

data MultiwayTree a Source #

A multiway tree is composed of a root element and a (possibly empty) set of successors which are multiway trees themselves. A multiway tree is never empty. The set of successor trees is sometimes called a forest.

Constructors

MultiwayTree a [MultiwayTree a]

Instances

Instances details

Generic (MultiwayTree a) Source #
Instance details Defined in Problems.MultiwayTrees Associated Types type Rep (MultiwayTree a) :: Type -> Type # Methods from :: MultiwayTree a -> Rep (MultiwayTree a) x # to :: Rep (MultiwayTree a) x -> MultiwayTree a #
Show a => Show (MultiwayTree a) Source #
Instance details Defined in Problems.MultiwayTrees Methods showsPrec :: Int -> MultiwayTree a -> ShowS # show :: MultiwayTree a -> String # showList :: [MultiwayTree a] -> ShowS #
NFData a => NFData (MultiwayTree a) Source #
Instance details Defined in Problems.MultiwayTrees Methods rnf :: MultiwayTree a -> () #
Eq a => Eq (MultiwayTree a) Source #
Instance details Defined in Problems.MultiwayTrees Methods (==) :: MultiwayTree a -> MultiwayTree a -> Bool # (/=) :: MultiwayTree a -> MultiwayTree a -> Bool #
type Rep (MultiwayTree a) Source #
Instance details Defined in Problems.MultiwayTrees type Rep (MultiwayTree a) = D1 ('MetaData "MultiwayTree" "Problems.MultiwayTrees" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'False) (C1 ('MetaCons "MultiwayTree" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [MultiwayTree a])))

multitree1 :: MultiwayTree Char Source #

Example of the following multiway tree.

single node 'a'

>>> multitree1 == MultiwayTree 'a' []
True

multitree2 :: MultiwayTree Char Source #

Example of the following multiway tree.

'a' has successor 'b'

>>> multitree2 == MultiwayTree 'a' [MultiwayTree 'b' []]
True

multitree3 :: MultiwayTree Char Source #

Example of the following multiway tree.

'a' has successor 'b', 'b' has successor 'c'

>>> multitree3 == MultiwayTree 'a' [MultiwayTree 'b' [MultiwayTree 'c' []]]
True

multitree4 :: MultiwayTree Char Source #

Example of the following multiway tree.

'b' has successors 'd', 'e'

>>> multitree4 == MultiwayTree 'b' [MultiwayTree 'd' [], MultiwayTree 'e' []]
True

multitree5 :: MultiwayTree Char Source #

Example of the following multiway tree.

'a' has successors 'f', 'c', 'b', and 'f' has successor 'g', and 'b' has successors 'd', 'e'

>>> :{
multitree5 == MultiwayTree 'a'
  [ MultiwayTree 'f' [MultiwayTree 'g' []]
  , MultiwayTree 'c' []
  , MultiwayTree 'b' [MultiwayTree 'd' [], MultiwayTree 'e' []]
  ]
:}
True

multitreeSize :: MultiwayTree a -> Int Source #

Returns the number of nodes in a multiway tree.

Examples

>>> multitreeSize multitree1
1

>>> multitreeSize multitree5
7

Notes

Expand

This was originally problem 70C. This is not included as a problem, to avoid a numbering conflict with the somewhat unrelated problem 70 in the original list, which is more interesting.