DAY 20
0
Software Development

## Functional Data Structure

``````fun <P1, P2, P3, R> ((P1, P2, P3) -> R).curried(): (P1) -> (P2) -> (P3) -> R {
return { p1: P1 ->
{ p2: P2 ->
{ p3: P3 ->
this(p1, p2, p3)
}
}
}
}

fun <P1, P2, P3, P4, R> ((P1, P2, P3, P4) -> R).curried(): (P1) -> (P2) -> (P3) -> (P4) -> R {
return { p1: P1 ->
{ p2: P2 ->
{ p3: P3 ->
{ p4: P4 ->
this(p1, p2, p3, p4)
}
}
}
}
}
``````

# ArrayList and LinkedList for immutable List

## Modifying

``````class LinkedList<T>(val head: Node<T>?)
class Node<T>(val value: T, val next: Node<T>?)

// "A" -> "B" -> "C" -> "D"
val a = LinkedList(Node("A", Node("B", Node("C", Node("D", null))))
// 新增一個 Z 在前面
"Z" -> "A" -> "B" -> "C" -> "D"

``````

``````val a = LinkedList(Node("A", Node("B", Node("C", Node("D", null))))
``````

Time complexity : [ArrayList] - O(n), [LinkedList] - O(1)
Space complexity: [ArrayList] - O(n), [LinkedList] - O(1)

# Create our own implementation

``````sealed class LinkedList<out T> {}

``````

``````"x | y" -> Sum Type
"(x, y)" -> Product Type

LinkedList = Nil | (T, LinkedList)    -> Sum Type and Product Type
``````

``````// ["A", "B", "C"]
val list1 = Cons("A", Cons("B"), Cons("C"))
// []
val list2 = Nil
// ["A", "B", "C", "D"]
val list3 = Cons("A", Cons("B"), Cons("C", Cons("D", Nil)))
``````

``````fun <T> linkedListOf(vararg values: T): LinkedList<T> {

return values.toList()
.reversed()
.asSequence()
.map { value -> consCreator.curried()(value) }
.fold( Nil as LinkedList<T> , { tail, creator -> creator(tail) })
}
``````

``````// [1, 2, 3]
val list1 = linkedListOf(1, 2, 3)
// ["A", "B", "C", "D"]
val list2 = linkedListOf("A", "B", "C", "D")
// Nil
``````

``````//Demo code for scala:
object Demo {
def main(args: Array[String]) {
val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums = Nil

println( "Tail of fruit : " + fruit.tail )
println( "Check if fruit is empty : " + fruit.isEmpty )
println( "Check if nums is empty : " + nums.isEmpty )
}
}

// Output
Tail of fruit : List(oranges, pears)
Check if fruit is empty : false
Check if nums is empty : true
``````

``````override fun toString(): String {
return when(this) {
is Cons -> {
var currentList = this
while (currentList is Cons) {
currentList = currentList.tail
if (currentList is Cons) {
result += ", "
}
}
"\$result)"
}
}
}
``````

``````fun isEmpty(): Boolean = this == Nil
``````

``````fun linkedListTest() {
val fruit = linkedListOf("apples", "oranges", "pears") as Cons<String>
val nums = Nil

println( "Tail of fruit : " + fruit.tail )
println( "Check if fruit is empty : " + fruit.isEmpty() )
println( "Check if nums is empty : " + nums.isEmpty() )
}
``````