PCM20210824_SICP_2.2.2_HierarchicalStructures.jl

### A Pluto.jl notebook ###
# v0.19.12

using Markdown
using InteractiveUtils

# ╔═╡ d04d7df0-04f9-11ec-36dc-8b535428902a
md"
======================================================================================
#### SICP: [2.2.2 Hierarchical Structures](https://sarabander.github.io/sicp/html/2_002e2.xhtml#g_t2_002e2_002e2)

###### file: PCM20210824\_SICP\_2.2.2\_HierarchicalStructures.jl

###### Julia/Pluto.jl-code (1.8.5/19.11) by PCM *** 2023/03/03 ***
======================================================================================
"

# ╔═╡ 79217d66-5068-4211-a848-b3a8eb5d7719
Atom = Union{Number, Symbol, Char, String}

# ╔═╡ 5c74f030-ab29-4f08-b1d5-cd85221d051f
md"
##### 2.2.2.1 SICP-Scheme-like *functional* but *typed* Julia
"

# ╔═╡ dd0551fe-def3-443a-b3a6-44fa40d6052c
md"
---
###### declaration of *composite* type $$Cons$$
"

# ╔═╡ 5d822320-3148-49f7-98e2-b631a21bbf90
struct Cons
	car
	cdr
end

# ╔═╡ dc887cc3-e2b4-4bc6-b781-844dd43d8781
md"
###### 1st (default) method of Scheme-like *constructor* function $$cons$$ with *untyped* input  
"

# ╔═╡ b02c31ac-9e45-492e-97fe-41601b602723
# idiomatic Julia with 1st (default) method of cons
cons(car::Any, cdr::Any)::Cons = Cons(car, cdr)::Cons   

# ╔═╡ c690eb5d-b921-4373-a3f4-34a0580554f6
md"
###### 1st (specialized) *typed* method of Scheme-like *selector* function $$car$$
"

# ╔═╡ ca05de56-fb03-4cf2-86ec-f749028c7309
# 1st method for car
car(cell::Cons) = cell.car

# ╔═╡ 6ae69d96-8097-42ba-8e73-be9bc4015332
md"
###### 1st (specialized) *typed* method of Scheme-like *selector* function $$cdr$$
"

# ╔═╡ 1fb40b33-47b7-4c26-ab58-1df36bbee490
cdr(cell::Cons)::Any = cell.cdr

# ╔═╡ 365e26e1-55fe-4633-a9c7-cb23759af772
md"
---
###### Comparison of Types

"

# ╔═╡ 2a1c5fbb-aa49-4f21-b638-d5852d2f3172
Atom <: Cons                         # ==> false -->  :)

# ╔═╡ 9408a58f-cc11-4682-bd5f-395bf1bc7d60
typeof(:nil) <: Atom                 # ==> true  -->  :)

# ╔═╡ 08c26d41-cf4b-4094-84e0-efea7882cac7
typeof(:nil) <: Cons                 # ==> false -->  :)

# ╔═╡ 86579050-bc57-45cf-965f-affabc23c6e0
md"
---
###### SICP-content in Julia

"

# ╔═╡ 8c38accf-8ca7-418e-aadb-f4c7aacc4eb4
md"""
---
                             +-----+-----+      +-----+-----+
                   l1 ------>|  o  |  o->|----->|  o  |  /  |
                             +--|--+-----+      +--|--+-----+
                                |                  | 
                            +-------+          +-------+
                            | :one  |          | "two" |
                            +-------+          +-------+

**Fig. 2.2.2.1** *Latent* Box- and Pointer Structure generated by $$l1 = cons(:one, cons(\text{"two"}, :nil))$$

---
"""

# ╔═╡ 6388d4e9-38a1-4f00-bbf0-e1a903083460
md"""
---


               l1 ----->o----->o----->:nil         l1 ----->o
                        |      |                           / \
                        |      |                          /   \  
                      :one   "two"                       /     o
                                                        /     / \
                                                       /     /   \
                                                    :one  "two" :nil

**Fig. 2.2.2.2** *Latent abstract* Binary Directed Trees generated by $$l1 = cons(:one, cons(\text{"two"}, :nil))$$

---
"""

# ╔═╡ 538d762c-ae92-4f1f-b5c7-41c541dc626d
md"""
---
                             +-----+-----+      +-----+-----+
                   l2 ------>|  o  |  o->|----->|  o  |  /  |
                             +--|--+-----+      +--|--+-----+
                                |                  | 
                            +-------+          +-------+
                            |   3   |          |  4.0  |
                            +-------+          +-------+

**Fig. 2.2.2.3** *Latent* Box- and Pointer Structure generated by $$l2 = cons(3, cons(4.0, :nil))$$

---
"""

# ╔═╡ d3d2ae26-c985-4856-bbb8-983d09b594ee
md"""
---


               l2 ----->o----->o----->:nil         l2 ----->o
                        |      |                           / \
                        |      |                          /   \  
                        3     4.0                        /     o
                                                        /     / \
                                                       /     /   \
                                                       3    4.0 :nil

**Fig. 2.2.2.4** *Latent abstract* Binary Directed Trees generated by $$l2 = cons(3, cons(4.0, :nil))$$

---
"""

# ╔═╡ 1cfbab4a-c1a8-49e9-bcc4-79ee773ead30
md"""
---
                  +-----+-----+
    binaryTree1-->|  o  |  o->|--------------------------->+
                  +--|--+-----+                            |
                     |                               +-----+-----+      +-----+-----+ 
                     |                     l2 ------>|  o  |  o->|----->|  o  |  /  |
                     |                               +--|--+-----+      +--|--+-----+ 
                     |                                  |                  | 
               +-----+-----+      +-----+-----+     +-------+          +-------+
     l1 ------>|  o  |  o->|----->|  o  |  /  |     |   3   |          |  4.0  |
               +--|--+-----+      +--|--+-----+     +-------+          +-------+ 
                  |                  | 
              +-------+          +-------+
              | :one  |          | "two" |
              +-------+          +-------+

**Fig. 2.2.2.5** (s.a. SICP, 1996, **Fig 2.5**) *Box- & Pointer*-structure generated by cons(l1, l2) 

---
"""

# ╔═╡ 0119977a-57e9-47a2-9c1b-48ddd4d62f90
md"""
---

                             l2
                              |
                              |
       binaryTree1 ---->o---->o---->o--->:nil     binaryTree1 ----->o
                        |     |     |                              / \       
                        |     |     |                             /   \
                        |     3    4.0                           /     \    l2
                        |                                       /       \   /
               l1 ----->o---->o---->:nil                       /         \ /
                        |     |                       l1 ---->o           o
                        |     |                              / \         / \
                      :one  "two"                           /   \       /   \
                                                        :one     o     3     o
                                                                / \         / \
                                                               /   \       /   \
                                                            "two"  :nil  4.0   :nil

                    PP(l1) ==> (:one, "two")
                    pp(l2) ==> (3, 4.0)
           pp(binaryTree1) ==> ((one, "two"), 3, 4.0)
   
          
**Fig. 2.2.2.6** (s.a. SICP, 1996, **Fig 2.6**) Graphical respresentations of *latent* binary tree implemented with *tuples* and generated by 'binaryTree1 = cons(l1, l2)' and our *manifest* Julia-list structures of binary trees

---
"""

# ╔═╡ 4b8e1599-eccd-4831-a864-c5e5dadd63fa
md"
###### 1st (default) *untyped* method of function 'pp' (= pretty print)
this method pretty-prints a *latent hierarchical* cons-structure as a *manifest nested* array structure
"

# ╔═╡ fbfcb81f-1741-4904-9b8e-c7890be30d71
md"
ASS (= Abelson, Sussman & Sussman) replace $nil$ by $'()$ (cf. SICP, 1996, p.101. So $'()$'s meaning is the empty list. 
Similarly we mark the 'end-of-list' in the *storage* structure ($Cons$*-structure*) as '*:nil*' and in its *manifestation* (*print*-list) as $()$.
"

# ╔═╡ 887c2e8d-08fc-4dce-9e1f-0938dea1623b
md"
---
##### Mapping over trees
"

# ╔═╡ 18c28f30-3a43-4041-82c7-421554469023
# =====================================================

# ╔═╡ 5e287813-4d57-48ad-a3e4-20247476512c
md"
---
#### 2.2.2.2 Idiomatic *imperative* or *typed* Julia
"

# ╔═╡ 4579401d-32ea-47a1-9f6a-c6af3b4a73ba
md"
##### Declaration of Scheme-like type $$Atom$$ as an $$Union$$-type
"

# ╔═╡ f4992192-d11f-4637-ae9f-dba7ae946ba8
typeof(:nil) <: Symbol <: Atom

# ╔═╡ 2e9de7fd-b00e-4ce1-ba68-d647497e57fe
md"
###### 2nd (specialized) *typed* method of Scheme-like *constructor* function $$cons$$ using Julia's $$Array$$
"

# ╔═╡ f7dabac5-0421-4581-8d87-00ce9d8eeeb1
md"
Now, *this* $cons$ constructs an array. This *cannot* be pretty-printed by $pp$

"

# ╔═╡ 41aef6dd-e5bd-44a7-9878-696a1a97e452
# idiomatic Julia with 2nd method of cons
function cons(car::Atom, list::Array)::Array
	pushfirst!(list, car)
end

# ╔═╡ 991b1ce6-a5ef-43ed-8999-32811fdbc344
md"
###### 2nd (specialized) *typed* method of Scheme-like *selector* function $$car$$ using Julia's $$Array$$
"

# ╔═╡ ec154684-ff2b-473c-8ffe-c40d03631091
# 2nd method for car
car(x::Array) = x[1]

# ╔═╡ 49c58521-2ca3-48ad-b3d3-ff6b66efad83
md"
###### 2nd (specialized) *typed* method of Scheme-like *selector* function $$cdr$$ using $$Array$$
"

# ╔═╡ 3444dab8-dd66-4bc3-bfb0-269ecd2f714a
cdr(x::Array) = x[2:end]

# ╔═╡ 5d4bf8f1-8b3c-41f3-ab41-711d56a30be3
function listLength(x)
	if x == :nil
		0
	elseif car(x) == :nil
		0
	else 
		1 + listLength(cdr(x))
	end # if
end

# ╔═╡ c219beca-688b-4642-be6d-adefc1448e44
#------------------------------------------------------------------------------------
# this method pretty-prints a latent hierarchical cons-structure as a nested 
#    tuple structure which has similarity with a Lisp- or Scheme-list
# also used in 3.3.1 and 3.3.2.1
#------------------------------------------------------------------------------------
function pp(consStruct)
	#--------------------------------------------------------------------------------
	function pp_iter(consStruct, arrayList)
		#----------------------------------------------------------------------------
		if consStruct == :nil                               # termination case 1 
			()
		elseif typeof(consStruct) <: Atom                   # termination case_2 
			consStruct
		#----------------------------------------------------------------------------
		# one-element list                                  # termination case_3 
		elseif (typeof(car(consStruct)) <: Atom) && (cdr(consStruct) == :nil)
			Tuple(push!(arrayList, pp(car(consStruct))))
		#----------------------------------------------------------------------------
		# flat multi-element list
		elseif (car(consStruct) == :nil) && (typeof(cdr(consStruct)) <: Cons)
			pp_iter(cdr(consStruct), push!(arrayList, ()))
		elseif (typeof(car(consStruct)) <: Atom) && (typeof(cdr(consStruct)) <: Cons)
			pp_iter(cdr(consStruct), push!(arrayList, car(consStruct)))
		#----------------------------------------------------------------------------
		# nested sublist as first element of multi-element list
			elseif (typeof(car(consStruct)) <: Cons) && (cdr(consStruct) == :nil)
				Tuple(push!(arrayList, pp(car(consStruct))))
		#----------------------------------------------------------------------------
		# nested sublist as first element of multi-element list
		elseif (typeof(car(consStruct)) <: Cons) && (typeof(cdr(consStruct)) <: Cons)
			pp_iter(cdr(consStruct), push!(arrayList, pp(car(consStruct))))
		#----------------------------------------------------------------------------
		else
			error("==> unknown case for: $consStruct")
		end # if
	end # pp_iter
	#--------------------------------------------------------------------------------
	pp_iter(consStruct, [])      
end # function pp
#------------------------------------------------------------------------------------

# ╔═╡ 5f36dae2-253b-4d86-97d6-2acde397e463
pp(:nil)                   # ==> () -->  :)

# ╔═╡ 18fa2ee8-8fd3-498c-bf72-4cae930fb4cf
pp(Cons(:one, :nil))       # ==>  (:one)

# ╔═╡ 31cd0a63-70f5-425d-bd2e-df9243a3198a
md"""
---

                             l4
                              |
                              |
       binaryTree 2---->o---->o---->o--->[]       binaryTree2 ----->o
                        |     |     |                              / \       
                        |     |     |                             /   \
                        |     3    4.0                           /     \    l4
                        |                                       /       \   /
               l3 ----->o---->o---->[]                         /         \ /
                        |     |                       l3 ---->o           o
                        |     |                              / \         / \
                      :one  "two"                           /   \       /   \
                                                        :one     o     3     o
                                                                / \         / \
                                                               /   \       /   \
                                                            "two"  []    4.0   []

                    Tuple(l3) := (:one, "two")
                    Tuple(l4) := (3, 4.0)
           Tuple(binaryTree2) := ((one, "two"), 3, 4.0)
   
          
**Fig. 2.2.2.7** (s.a. SICP, 1996, Fig 2.6) Graphical respresentations of *latent* binary tree implemented with *arrays* and generated by 'binaryTree2 = cons(l3, l4)' and *manifest* list structures of binary trees

---
"""

# ╔═╡ 17532169-afb2-474e-85db-1789c9b3db8e
supertype(AbstractString) 

# ╔═╡ 541eecaa-26aa-4a31-906b-c177065e3f21
md"
###### 1st (default) method of *constructor* function 'list' with *untyped* input and constructing *arrays*
"

# ╔═╡ d158f290-f890-422b-b978-c92cdfeb358f
list2(xs::Any...)::Array = [xs::Any...]::Array  # slurping and splatting

# ╔═╡ 69bce858-176d-4764-a553-1ffe7b26319f
list2()

# ╔═╡ cdd7254a-bae0-489c-82f4-bbc9b93a8ea1
Tuple(list2())

# ╔═╡ d06e076c-9665-4b7a-b4f3-e26b055bc717
lOne = list2(:one, "two")

# ╔═╡ 0d88594c-6dfc-4e43-85e0-0980834983d0
Tuple(lOne)

# ╔═╡ 278e1371-d51f-4db0-a39e-12e2be14da40
lTwo = list2(3, 4.0)

# ╔═╡ a141433d-227f-4f15-98a5-f3d04e40fe99
Tuple(lTwo)

# ╔═╡ 481d9d41-2487-4b1d-8752-04fbf1f15766
binaryTree3 = list2(list2(:one, "two"), 3, 4.0)     # compare SICP, Fig. 2.6

# ╔═╡ 333b5c86-34ed-473c-b30a-f23b0735d2a2
Tuple(binaryTree3)                      # makes tuples only on top level

# ╔═╡ 72cfcaa3-a5b1-484a-9829-d2bd3024f90b
md"
###### 3rd (specialized) *typed* method of *constructor* function 'cons'
"

# ╔═╡ caebe503-a0a2-4782-aea3-7456ac3ea1a6
# idiomatic Julia with 3rd method of cons
function cons(list1::Array, list2::Array)::Array
	list1 = push!([], list1)
	append!(list1, list2)
end

# ╔═╡ 786c0bd8-932f-46a3-9cd3-11a626f523fc
l1 = cons(:one, cons("two", :nil))

# ╔═╡ 4c7e2d00-0f28-420f-9ae1-466fcce85cf3
pp(l1)            # ==> (:one, "two") -->  :)

# ╔═╡ 715f429d-7656-4014-aebf-974ed05f0cc1
car(l1)

# ╔═╡ a5ef6c4b-b6c5-4ad8-ac43-ea4a204deadd
cdr(l1)                # ==> Cons("two", :nil) -->   :)

# ╔═╡ 76ca37f6-71ba-4320-aa19-1e73f53bb65d
pp(cdr(l1))            # ==> ("two") -->   :)

# ╔═╡ d046b762-098f-4c26-b57b-6f4ee7497032
car(cdr(l1))

# ╔═╡ 4ae9e932-644e-4bdd-8b0c-2aa4e5910802
l1

# ╔═╡ 97b87ad4-f74c-483f-8777-690ebd82bdef
pp(l1)                                 # ==> (:one, "two") -->  :)

# ╔═╡ f5a5cb9b-5148-43e3-aea2-9e62a23ca471
l2 = cons(3, cons(4.0, :nil))   # ==> Cons(3, Cons(4.0, :nil))

# ╔═╡ 8550486d-a796-46d3-a8fd-07e0a7f294bd
pp(l2)                          # ==> (3, 4.0) -->  :)

# ╔═╡ 286754b5-505d-43a4-99b9-aa57f789dea4
car(l2)

# ╔═╡ a3571fdb-fa31-4db6-b6f3-c71d7f2e94e0
cdr(l2)                          # ==> Cons(4.0, :nil)

# ╔═╡ b9a5c6e4-7f67-42e4-9380-6d999a3df17d
pp(cdr(l2))                      # ==> Cons(4.0, :nil) ==> (4.0) -->  :)

# ╔═╡ 88ee71e8-4b91-4a27-ab79-7dd6fbe49aa7
car(cdr(l2))

# ╔═╡ bc81d8ad-7477-48fd-8a89-a673f815562e
l1, l2                               # arguments are left intact !

# ╔═╡ 4e37baa6-44e5-40ce-84e4-7ac943122bc5
pp(l2)                                 # ==> (3, 4.0) -->  :)

# ╔═╡ cc9478f7-5e21-4c2f-9569-56215f5f2565
# works with 1st method of cons
binaryTree1 = cons(l1, l2)           # similar to SICP, Fig. 2.5

# ╔═╡ 882e4324-afd3-42a2-90a0-58da4a21fad9
binaryTree1    # ==> Cons(Cons(:one, Cons("two", :nil)), Cons(3, Cons(4.0, :nil)))

# ╔═╡ ad034edc-d673-40a0-82e7-35803a5ecffe
pp(binaryTree1)                      # ==> ((:one, "two"), 3, 4.0)

# ╔═╡ ad0ac826-330d-43bd-b86f-7a13d591057e
car(binaryTree1)                     # ==> Cons(:one, Cons("two", :nil))

# ╔═╡ 1ce376af-a0c2-400f-a655-41ae0bdab251
pp(car(binaryTree1))                 # ==> (:one, "two") -->  :)

# ╔═╡ 73c07fcb-5aa3-45b7-abd1-50e2af4b095c
cdr(binaryTree1)                     # ==> Cons(3, Cons(4.0, :nil))

# ╔═╡ 746146a0-10f1-44f1-a73b-92c62fe574b2
pp(cdr(binaryTree1))                 # ==> (3, 4.0) -->  :)

# ╔═╡ d9a102a8-99cb-42d4-b7f6-7b04b2eddd70
car(car(binaryTree1))

# ╔═╡ 0df51397-7df5-49a8-9fb1-c686a548546e
car(cdr(car(binaryTree1)))

# ╔═╡ 5e271af9-a6d5-4366-a8be-d29615a56990
car(cdr(binaryTree1))

# ╔═╡ 21eab018-1d2b-405c-bb13-aac7d61f0586
car(cdr(cdr(binaryTree1)))

# ╔═╡ 38f2fe0a-901d-491d-8b49-8596cae6d8f5
pp(binaryTree1)                        # ==> ((:one, "two"), 3, 4.0)

# ╔═╡ 682249be-d6ea-4f86-9c52-d3931b7cb613
list(elements...) = 
	if ==(elements, ())
		cons(:nil, :nil)
	elseif ==(lastindex(elements), 1)
		cons(elements[1], :nil)
	else
		cons(elements[1], list(elements[2:end]...))
	end #if

# ╔═╡ 7d470294-9c69-4ab8-82da-e8a2a7c5b576
list(())                   # ==> Cons((), :nil)

# ╔═╡ 171ab6fa-048e-4330-a506-045f1523dc8a
pp(list())                 # ==> Cons((), :nil) ==> (()) -->  :)

# ╔═╡ 803803c4-b675-4003-af82-bd017318bf81
list(:one)                 # ==> Cons(:one, :nil) -->  :)

# ╔═╡ d1af268e-309d-49ba-a9f7-170f7be73669
pp(list(:one))             # ==> Cons(:one, :nil) ==> (:one)  -->    :) 

# ╔═╡ fd74dd1e-c197-444f-9d3a-796426884648
list(:one, "two")          # ==> Cons(:one, Cons("two", :nil))

# ╔═╡ f9570f49-7923-469e-925c-9ed0f33bc163
pp(list(:one, "two"))      # ==> (:one, "two") -->  :)

# ╔═╡ 5758cda8-317f-41f7-87fc-bf53998d4fc6
list(list(:one, "two"))                # ==> Cons(Cons(:one, Cons("two", :nil)), :nil)

# ╔═╡ 2ab796bc-449d-4386-aaf2-20615bf1281e
# ==> Cons(Cons(:one, Cons("two", :nil)), Cons(3, Cons(4.0, :nil)))  
#      --> equivalent to binaryTree1
list(list(:one, "two"), 3, 4.0) 

# ╔═╡ ffbed260-a5e3-4906-85db-f6debea5b00d
pp(list(list(:one, "two"), 3, 4.0))    # ==> ((:one, "two"), 3, 4.0) -->  :)

# ╔═╡ ea483827-a735-4cfa-85fd-75cf2fe910f4
pp(list(list(:one, "two")))            # ==> ((:one, "two")) -->  :)

# ╔═╡ 7e4dad09-01ef-4bc6-8bdb-507ab580a2e7
pp(list(list(list(:one, "two")), 3, 4.0)) 
                                       # ==> (((:one, "two")), 3, 4.0) --> :)

# ╔═╡ 60f45d12-55d9-4e07-b841-8e68f010428a
list(list(list(:one, "two")), list(list(3), 4.0))

# ╔═╡ ef0f3822-5ec3-4d54-a518-7100a2820d87
pp(list(list(list(:one, "two")), list(list(3), 4.0)))

# ╔═╡ fcaf4ffc-ab66-4052-bc07-cb0cf7379f0a
x = cons(list(:one, "two"), list(3, 4.0))  #  SICP, 1996, p. 108

# ╔═╡ a8db6a56-0a67-434d-bc42-4ce0db57f2a2
binaryTree1 == x                  # binaryTree1 and x are equal 

# ╔═╡ 638ba491-dd79-43e2-a6de-46382d99e77f
pp(x)                             # ==> ((:one, "two"), 3, 4.0)

# ╔═╡ b99a3642-466f-439e-928b-257a525a9e2b
listLength(x)

# ╔═╡ c9300481-e4be-4827-8f73-ac9a8fe406b5
x

# ╔═╡ 0f45f9a6-6877-42fc-83e2-377d1758d401
pp(x)

# ╔═╡ 8830c7df-e37c-4f81-879d-3ded6267e266
list(x, x)

# ╔═╡ f7797441-d376-4a56-b837-a488c3742ea5
list(list(x, x), list(x, x))

# ╔═╡ 3e662ba4-b303-4093-9d15-999140ff0d18
pp(list(list(x, x), list(x, x)))

# ╔═╡ dd325dc8-884b-4c0f-9d55-45aa2cbf3a87
listLength(list(x, x))

# ╔═╡ be1f7a7f-618b-4525-b796-78a5d1d1e54a
pp(cons(:nil, :nil))       # ==> (()) -->  :)

# ╔═╡ 30e97964-4c4a-430a-afe5-46e6a387fd1f
function scale_tree(tree, factor)
	#---------------------------------------------
	null(x) = x == :nil
	isnumber(x::Any) = typeof(x) <: Number
	isvector(x::Any) = typeof(x) == Vector{Any}
	#---------------------------------------------
	if null(tree)
		:nil
	elseif isnumber(car(tree))
		cons(factor * car(tree), scale_tree(cdr(tree), factor))
	else 
		cons(scale_tree(car(tree), factor), scale_tree(cdr(tree), factor))
	end
end

# ╔═╡ c32f258c-1b0d-418f-b682-27566177b152
scale_tree(list(1, list(2, list(3, 4), 5), list(6, 7)), 10)

# ╔═╡ 35e18b20-cc3c-49b2-8de4-60450163a772
pp(scale_tree(list(1, list(2, list(3, 4), 5), list(6, 7)), 10))

# ╔═╡ a33ffcf7-7e38-49c9-83b7-64b1794d8bf8
l3 = cons(:one, cons("two", []))

# ╔═╡ e35dbec5-abbd-4604-8295-f33ac7e2a186
pp(l3)   # ==> "unknown case" because l3 is an array

# ╔═╡ 83b6eb9c-0e9d-4a4c-bc29-320ebf41ed35
Tuple(l3)

# ╔═╡ bdbece9a-2902-4849-9631-e66523be86ab
Tuple(l3)

# ╔═╡ 1265e29f-5935-4d42-945c-39055ab96870
l4 = cons(3, cons(4.0, []))

# ╔═╡ 72c1a55e-0f01-467b-8dfb-d35bfabe2c3a
Tuple(l4)

# ╔═╡ d73af3eb-5829-481c-be11-9f83a5b98c65
l3, l4                            # arguments are left intact !

# ╔═╡ 49f3d8e8-2b40-4532-88aa-35711ef97497
binaryTree2 = cons(l3, l4)           # compare SICP, Fig. 2.6

# ╔═╡ 02342aa2-29a3-4274-b345-38dc17ab0eef
# works with 3rd method of cons
x2 = cons(lOne, lTwo)                   # compare SICP, Fig. 2.6

# ╔═╡ f1a88238-cd46-4c81-927c-80881d9c3ca3
Tuple(x2)                               # makes tuples only on top level

# ╔═╡ dcab3c59-cef3-47c1-8f07-31da3816feba
x2

# ╔═╡ 04a31959-b5a8-4283-a5e9-e6bb8822dbf2
Tuple(x2)                               # makes tuples only on top level

# ╔═╡ a5843028-cfa1-4d42-a2ed-3eb2e337389e
car(x2)

# ╔═╡ eeb9b7e4-1bd1-4f08-ad33-70b1b05bbaef
car(car(x2))

# ╔═╡ a59a0629-c827-4bcf-8598-d389f76d546d
car(cdr(car(x2)))

# ╔═╡ 6b754818-d7e8-4955-9a74-616f32fb98cc
car(cdr(x2))

# ╔═╡ ae38a6d9-8285-4093-b796-53668427d464
car(cdr(cdr(x2)))

# ╔═╡ ec4c39b2-54d7-4659-8c35-f823bfec550e
length(x2)

# ╔═╡ 0387258c-3a71-4f39-bd08-9ee2ce0c425e
list2(x2, x2)

# ╔═╡ d5f4cf53-02ed-4a5e-ac87-286e02bbfde9
length(list2(x2, x2))               # Julia's array length function

# ╔═╡ eead7754-f10f-4fbe-89df-6c97d13d3868
md"
##### Declaration of type $$AtomOrCons$$ as an $$Union$$-type
"

# ╔═╡ 7af5cbee-55ac-404e-89c8-55eb51f3431f
AtomOrCons = Union{Atom, Cons}

# ╔═╡ 4021581a-03fb-4f5a-89ce-02bba90c658b
md"
###### 1st (specialized) *typed* method of function 'count_leaves'
"

# ╔═╡ 328129f3-e72b-43b4-a41a-5aa6153e585b
# count leaves in binary Cons-Trees
function count_leaves(x::AtomOrCons)::Signed
	#-----------------------------------------
	null(x) = x == :nil
	#-----------------------------------------
	if null(x)
		0
	elseif !(typeof(x) == Cons)
		1
	else
		count_leaves(car(x)) + count_leaves(cdr(x)) 
	end
end

# ╔═╡ de73fef3-597d-466d-a792-57920f20e613
md"
###### 2nd (specialized) *typed* method of function $$count\_leaves$$
"

# ╔═╡ 21aa84f9-c401-434e-adac-05cf0f869d01
# count leaves in binary trees as Julia arrays
function count_leaves(x::Array)::Signed
	#-----------------------------------------
	null(x) = x == []
	#-----------------------------------------
	if null(x)
		0
	else
		count_leaves(car(x)) + count_leaves(cdr(x))
	end
end

# ╔═╡ fde686c0-6810-48ae-b55f-855d8e532908
count_leaves(x)

# ╔═╡ db20e792-2252-4703-ae63-9fae428d6375
count_leaves(list(x, x))

# ╔═╡ 910e7d3f-efa4-4212-a384-010131b27715
count_leaves(x2)

# ╔═╡ fa40277a-ddc9-4538-9746-c6845b67e415
count_leaves(list2(x2, x2))

# ╔═╡ 8e742303-efdc-4642-a209-191e18aa261c
count_leaves(l1)

# ╔═╡ 3df46b08-f9eb-4589-9d39-06cba4c9923e
count_leaves(binaryTree1)

# ╔═╡ 8f39a3e5-024b-4e8a-b68c-52cf746c1870
count_leaves(binaryTree2)

# ╔═╡ 187a562d-9a82-4499-9a8f-d8f7e4ec454c
count_leaves(binaryTree3)

# ╔═╡ 7998e4b3-2f0f-49f7-9c8c-4dbd37c4fb7d
count_leaves([])

# ╔═╡ 9d12cb69-4bc2-4aff-9166-20b5787d704b
typeof(car([:one])) == AtomOrCons 

# ╔═╡ 7fa8eb9c-6ebc-43a9-9102-e3e8802ee556
count_leaves([:one])

# ╔═╡ e52a4602-b83a-4d6c-a54d-35401e5fb068
count_leaves([:one, "two"])

# ╔═╡ f51af477-c809-4f07-a38f-538ac6b00ec8
md"
---
##### Mapping over trees
"

# ╔═╡ 1489b23b-aa5c-4812-9914-56db0979fa50
function scale_tree2(tree::Vector, factor::Number)
	#---------------------------------------------
	null = isempty
	isnumber(x::Any) = typeof(x) <: Number
	isvector(x::Any) = typeof(x) == Vector{Any}
	#---------------------------------------------
	if null(tree)
		tree
	elseif isnumber(car(tree))
		cons(factor * car(tree), scale_tree2(cdr(tree), factor))
	else 
		cons(scale_tree2(car(tree), factor), scale_tree2(cdr(tree), factor))
	end
end

# ╔═╡ 3014af89-278f-426c-a4a3-46840dd86e9b
l5 = list2(1, list2(2, list2(3, 4), 5), list2(6, 7))

# ╔═╡ 9f7aeced-191e-4a92-a27b-0d02a321dfc3
scale_tree2(l5, 10)

# ╔═╡ 404a4b60-2cc2-40d5-ada8-9a020bd200a5
function scale_tree3(tree::Array, factor::Number)
	#---------------------------------------------
	isnumber(x::Any) = typeof(x) <: Number
	isarray(x::Any)  = typeof(x) == Array{Any}
	#---------------------------------------------
	map(subtree->
		if isnumber(subtree)
			subtree * factor
		else
			scale_tree3(subtree, factor) 
		end, tree)
end

# ╔═╡ ae7f3fcc-886f-4b06-8e20-371b8a0cf5cb
scale_tree3(l5, 10)

# ╔═╡ f84c82c9-d004-497c-9f64-71c9e3f7219d
function scale_tree4(tree::Array, factor::Number)
	#---------------------------------------------
	isnumber(x::Any) = typeof(x) <: Number
	isarray(x::Any)  = typeof(x) == Array{Any}
	#---------------------------------------------
	map(tree) do subtree
		if isnumber(subtree)
			subtree * factor
		else
			scale_tree4(subtree, factor) 
		end # if
	end # do
end

# ╔═╡ 47701d24-b015-452d-9b53-6ef244a27860
scale_tree4(l5, 10)

# ╔═╡ 0802559e-7777-43fb-a2ea-1b21a68bd034
md"
---
##### References
- **Abelson, H., Sussman, G.J. & Sussman, J.**; Structure and Interpretation of Computer Programs, Cambridge, Mass.: MIT Press, (2/e), 1996, [https://sarabander.github.io/sicp/](https://sarabander.github.io/sicp/), last visit 2022/09/04
"

# ╔═╡ 51873a3d-f856-4f7b-8fd6-4270445ac525
md"
---
##### end of ch. 2.2.2
====================================================================================

This is a **draft** under the [Attribution-NonCommercial-ShareAlike 4.0 International **(CC BY-NC-SA 4.0)**](https://creativecommons.org/licenses/by-nc-sa/4.0/) license. Comments, suggestions for improvement and bug reports are welcome: **claus.moebus(@)uol.de**

====================================================================================
"

# ╔═╡ 00000000-0000-0000-0000-000000000001
PLUTO_PROJECT_TOML_CONTENTS = """
[deps]
"""

# ╔═╡ 00000000-0000-0000-0000-000000000002
PLUTO_MANIFEST_TOML_CONTENTS = """
# This file is machine-generated - editing it directly is not advised

julia_version = "1.8.5"
manifest_format = "2.0"
project_hash = "da39a3ee5e6b4b0d3255bfef95601890afd80709"

[deps]
"""

# ╔═╡ Cell order:
# ╟─d04d7df0-04f9-11ec-36dc-8b535428902a
# ╠═79217d66-5068-4211-a848-b3a8eb5d7719
# ╟─5c74f030-ab29-4f08-b1d5-cd85221d051f
# ╟─dd0551fe-def3-443a-b3a6-44fa40d6052c
# ╠═5d822320-3148-49f7-98e2-b631a21bbf90
# ╟─dc887cc3-e2b4-4bc6-b781-844dd43d8781
# ╠═b02c31ac-9e45-492e-97fe-41601b602723
# ╟─c690eb5d-b921-4373-a3f4-34a0580554f6
# ╠═ca05de56-fb03-4cf2-86ec-f749028c7309
# ╟─6ae69d96-8097-42ba-8e73-be9bc4015332
# ╠═1fb40b33-47b7-4c26-ab58-1df36bbee490
# ╟─365e26e1-55fe-4633-a9c7-cb23759af772
# ╠═2a1c5fbb-aa49-4f21-b638-d5852d2f3172
# ╠═9408a58f-cc11-4682-bd5f-395bf1bc7d60
# ╠═08c26d41-cf4b-4094-84e0-efea7882cac7
# ╟─86579050-bc57-45cf-965f-affabc23c6e0
# ╟─8c38accf-8ca7-418e-aadb-f4c7aacc4eb4
# ╠═786c0bd8-932f-46a3-9cd3-11a626f523fc
# ╠═4c7e2d00-0f28-420f-9ae1-466fcce85cf3
# ╟─6388d4e9-38a1-4f00-bbf0-e1a903083460
# ╠═715f429d-7656-4014-aebf-974ed05f0cc1
# ╠═a5ef6c4b-b6c5-4ad8-ac43-ea4a204deadd
# ╠═76ca37f6-71ba-4320-aa19-1e73f53bb65d
# ╠═d046b762-098f-4c26-b57b-6f4ee7497032
# ╟─538d762c-ae92-4f1f-b5c7-41c541dc626d
# ╠═f5a5cb9b-5148-43e3-aea2-9e62a23ca471
# ╠═8550486d-a796-46d3-a8fd-07e0a7f294bd
# ╟─d3d2ae26-c985-4856-bbb8-983d09b594ee
# ╠═286754b5-505d-43a4-99b9-aa57f789dea4
# ╠═a3571fdb-fa31-4db6-b6f3-c71d7f2e94e0
# ╠═b9a5c6e4-7f67-42e4-9380-6d999a3df17d
# ╠═88ee71e8-4b91-4a27-ab79-7dd6fbe49aa7
# ╟─1cfbab4a-c1a8-49e9-bcc4-79ee773ead30
# ╠═cc9478f7-5e21-4c2f-9569-56215f5f2565
# ╠═882e4324-afd3-42a2-90a0-58da4a21fad9
# ╠═ad034edc-d673-40a0-82e7-35803a5ecffe
# ╠═ad0ac826-330d-43bd-b86f-7a13d591057e
# ╠═1ce376af-a0c2-400f-a655-41ae0bdab251
# ╠═73c07fcb-5aa3-45b7-abd1-50e2af4b095c
# ╠═746146a0-10f1-44f1-a73b-92c62fe574b2
# ╠═d9a102a8-99cb-42d4-b7f6-7b04b2eddd70
# ╠═0df51397-7df5-49a8-9fb1-c686a548546e
# ╠═5e271af9-a6d5-4366-a8be-d29615a56990
# ╠═21eab018-1d2b-405c-bb13-aac7d61f0586
# ╠═bc81d8ad-7477-48fd-8a89-a673f815562e
# ╟─0119977a-57e9-47a2-9c1b-48ddd4d62f90
# ╠═4ae9e932-644e-4bdd-8b0c-2aa4e5910802
# ╠═97b87ad4-f74c-483f-8777-690ebd82bdef
# ╠═4e37baa6-44e5-40ce-84e4-7ac943122bc5
# ╠═38f2fe0a-901d-491d-8b49-8596cae6d8f5
# ╠═682249be-d6ea-4f86-9c52-d3931b7cb613
# ╠═fcaf4ffc-ab66-4052-bc07-cb0cf7379f0a
# ╠═a8db6a56-0a67-434d-bc42-4ce0db57f2a2
# ╠═638ba491-dd79-43e2-a6de-46382d99e77f
# ╠═5d4bf8f1-8b3c-41f3-ab41-711d56a30be3
# ╠═b99a3642-466f-439e-928b-257a525a9e2b
# ╠═fde686c0-6810-48ae-b55f-855d8e532908
# ╟─4b8e1599-eccd-4831-a864-c5e5dadd63fa
# ╠═c219beca-688b-4642-be6d-adefc1448e44
# ╟─fbfcb81f-1741-4904-9b8e-c7890be30d71
# ╠═5f36dae2-253b-4d86-97d6-2acde397e463
# ╠═be1f7a7f-618b-4525-b796-78a5d1d1e54a
# ╠═7d470294-9c69-4ab8-82da-e8a2a7c5b576
# ╠═171ab6fa-048e-4330-a506-045f1523dc8a
# ╠═803803c4-b675-4003-af82-bd017318bf81
# ╠═18fa2ee8-8fd3-498c-bf72-4cae930fb4cf
# ╠═d1af268e-309d-49ba-a9f7-170f7be73669
# ╠═fd74dd1e-c197-444f-9d3a-796426884648
# ╠═f9570f49-7923-469e-925c-9ed0f33bc163
# ╠═5758cda8-317f-41f7-87fc-bf53998d4fc6
# ╠═2ab796bc-449d-4386-aaf2-20615bf1281e
# ╠═ffbed260-a5e3-4906-85db-f6debea5b00d
# ╠═ea483827-a735-4cfa-85fd-75cf2fe910f4
# ╠═7e4dad09-01ef-4bc6-8bdb-507ab580a2e7
# ╠═60f45d12-55d9-4e07-b841-8e68f010428a
# ╠═ef0f3822-5ec3-4d54-a518-7100a2820d87
# ╠═c9300481-e4be-4827-8f73-ac9a8fe406b5
# ╠═0f45f9a6-6877-42fc-83e2-377d1758d401
# ╠═8830c7df-e37c-4f81-879d-3ded6267e266
# ╠═f7797441-d376-4a56-b837-a488c3742ea5
# ╠═3e662ba4-b303-4093-9d15-999140ff0d18
# ╠═dd325dc8-884b-4c0f-9d55-45aa2cbf3a87
# ╠═db20e792-2252-4703-ae63-9fae428d6375
# ╟─887c2e8d-08fc-4dce-9e1f-0938dea1623b
# ╠═30e97964-4c4a-430a-afe5-46e6a387fd1f
# ╠═18c28f30-3a43-4041-82c7-421554469023
# ╠═c32f258c-1b0d-418f-b682-27566177b152
# ╠═35e18b20-cc3c-49b2-8de4-60450163a772
# ╟─5e287813-4d57-48ad-a3e4-20247476512c
# ╟─4579401d-32ea-47a1-9f6a-c6af3b4a73ba
# ╠═f4992192-d11f-4637-ae9f-dba7ae946ba8
# ╟─2e9de7fd-b00e-4ce1-ba68-d647497e57fe
# ╟─f7dabac5-0421-4581-8d87-00ce9d8eeeb1
# ╠═41aef6dd-e5bd-44a7-9878-696a1a97e452
# ╟─991b1ce6-a5ef-43ed-8999-32811fdbc344
# ╠═ec154684-ff2b-473c-8ffe-c40d03631091
# ╟─49c58521-2ca3-48ad-b3d3-ff6b66efad83
# ╠═3444dab8-dd66-4bc3-bfb0-269ecd2f714a
# ╠═a33ffcf7-7e38-49c9-83b7-64b1794d8bf8
# ╠═e35dbec5-abbd-4604-8295-f33ac7e2a186
# ╠═83b6eb9c-0e9d-4a4c-bc29-320ebf41ed35
# ╠═1265e29f-5935-4d42-945c-39055ab96870
# ╠═72c1a55e-0f01-467b-8dfb-d35bfabe2c3a
# ╠═49f3d8e8-2b40-4532-88aa-35711ef97497
# ╟─31cd0a63-70f5-425d-bd2e-df9243a3198a
# ╠═d73af3eb-5829-481c-be11-9f83a5b98c65
# ╠═17532169-afb2-474e-85db-1789c9b3db8e
# ╠═bdbece9a-2902-4849-9631-e66523be86ab
# ╟─541eecaa-26aa-4a31-906b-c177065e3f21
# ╠═d158f290-f890-422b-b978-c92cdfeb358f
# ╠═69bce858-176d-4764-a553-1ffe7b26319f
# ╠═cdd7254a-bae0-489c-82f4-bbc9b93a8ea1
# ╠═d06e076c-9665-4b7a-b4f3-e26b055bc717
# ╠═0d88594c-6dfc-4e43-85e0-0980834983d0
# ╠═278e1371-d51f-4db0-a39e-12e2be14da40
# ╠═a141433d-227f-4f15-98a5-f3d04e40fe99
# ╠═481d9d41-2487-4b1d-8752-04fbf1f15766
# ╠═333b5c86-34ed-473c-b30a-f23b0735d2a2
# ╟─72cfcaa3-a5b1-484a-9829-d2bd3024f90b
# ╠═caebe503-a0a2-4782-aea3-7456ac3ea1a6
# ╠═02342aa2-29a3-4274-b345-38dc17ab0eef
# ╠═f1a88238-cd46-4c81-927c-80881d9c3ca3
# ╠═dcab3c59-cef3-47c1-8f07-31da3816feba
# ╠═04a31959-b5a8-4283-a5e9-e6bb8822dbf2
# ╠═a5843028-cfa1-4d42-a2ed-3eb2e337389e
# ╠═eeb9b7e4-1bd1-4f08-ad33-70b1b05bbaef
# ╠═a59a0629-c827-4bcf-8598-d389f76d546d
# ╠═6b754818-d7e8-4955-9a74-616f32fb98cc
# ╠═ae38a6d9-8285-4093-b796-53668427d464
# ╠═ec4c39b2-54d7-4659-8c35-f823bfec550e
# ╠═910e7d3f-efa4-4212-a384-010131b27715
# ╠═0387258c-3a71-4f39-bd08-9ee2ce0c425e
# ╠═d5f4cf53-02ed-4a5e-ac87-286e02bbfde9
# ╠═fa40277a-ddc9-4538-9746-c6845b67e415
# ╟─eead7754-f10f-4fbe-89df-6c97d13d3868
# ╠═7af5cbee-55ac-404e-89c8-55eb51f3431f
# ╟─4021581a-03fb-4f5a-89ce-02bba90c658b
# ╠═328129f3-e72b-43b4-a41a-5aa6153e585b
# ╠═8e742303-efdc-4642-a209-191e18aa261c
# ╠═3df46b08-f9eb-4589-9d39-06cba4c9923e
# ╠═8f39a3e5-024b-4e8a-b68c-52cf746c1870
# ╠═187a562d-9a82-4499-9a8f-d8f7e4ec454c
# ╟─de73fef3-597d-466d-a792-57920f20e613
# ╠═21aa84f9-c401-434e-adac-05cf0f869d01
# ╠═7998e4b3-2f0f-49f7-9c8c-4dbd37c4fb7d
# ╠═9d12cb69-4bc2-4aff-9166-20b5787d704b
# ╠═7fa8eb9c-6ebc-43a9-9102-e3e8802ee556
# ╠═e52a4602-b83a-4d6c-a54d-35401e5fb068
# ╟─f51af477-c809-4f07-a38f-538ac6b00ec8
# ╠═1489b23b-aa5c-4812-9914-56db0979fa50
# ╠═3014af89-278f-426c-a4a3-46840dd86e9b
# ╠═9f7aeced-191e-4a92-a27b-0d02a321dfc3
# ╠═404a4b60-2cc2-40d5-ada8-9a020bd200a5
# ╠═ae7f3fcc-886f-4b06-8e20-371b8a0cf5cb
# ╠═f84c82c9-d004-497c-9f64-71c9e3f7219d
# ╠═47701d24-b015-452d-9b53-6ef244a27860
# ╟─0802559e-7777-43fb-a2ea-1b21a68bd034
# ╟─51873a3d-f856-4f7b-8fd6-4270445ac525
# ╟─00000000-0000-0000-0000-000000000001
# ╟─00000000-0000-0000-0000-000000000002