CS Fundamentals But make it Typescript & Functional

this is a redo from this post https://codeburst.io/cs-with-js-linked-list-e27008cfc9d9 by Xiaoyun Yang

But I'm using my 2 weeks of typescript skills and my 4 chapters of this book https://www.amazon.com/Functional-Programming-JavaScript-Dan-Mantyla/dp/1784398225

This post will have functions that return List Nodes.

Create a List Node from a value

type ListNode = {
    value: number | string
    next: ListNode | null
}

const createList = (value: number | string): ListNode => ({ value, next: null })

Kudos to typescript that it can have a property in a type that is the same type that holds the property.

That first function would return
createlist(1) // { value: 1, next: null }

Add a list as a tail of another list

Lets try to get this

const list = createList(1)
addTail(2, list) // { value: 1, next: { value:2 next: null } }

Lets define that addTail(): ListNode

const addTail = 
(value: number | string, list: ListNode): ListNode => {
    const copyList = { ...list}

    const addToNext = 
(value: number | string, listCopy: ListNode): ListNode => {
        if (listCopy.next === null) {
            listCopy.next = createList(value)
            return listCopy
        } else {
            addToNext(value, listCopy.next)
            return listCopy
        }
    }
    return addToNext(value, copyList)
}

This functions is using "divide and conquer"
Where divide is a recursion, a conquer is getting a list.value === null

Add to Head

Lets try to get this

const list = createList(1)
addHead(0, list) // { value: 0, next: { value: 1, next: null } }

Lets define that addHead(): ListNode

const addHead = ({ value, list}: ListNodeArgs): ListNode => {
    const head = createList(value)
    head.next = { ...list}
    return head
}

Here the functions builds a new function from the value param and adds to head.next a copy of the list param
head.next = { ...list}

Remove from head

const removeHead = (list: ListNode): ListNode | null => list.next

Create a Linked list from an Array

Lets try to get this

const array1 = ['a', 'b', 'c']
createListNodeFromArray(array1) // Returns:
// { value: 'a', next: 
// { value: 'b', next: 
// { value: 'c', next: null } } }

Lets define that createListNodeFromArray(): ListNode

const createListNodeFromArray = (arr: string[] | number[]): ListNode => {
    let newList: ListNode | null = null
    arr.map((item: string | number) => {
        if (newList === null) {
            newList = createList(item)
        } else {
            newList = addTail(item, newList )
        }
    })
    return newList as unknown as ListNode
}

In here the function will map over the items in the array, and fill them in a null object type ListNode | null

2 conditions

1. If the list is null lets use the createList(item)
2. Else lets use the addTail(item)

Zip

Zip is like that section of a map in Zelda where is better to go after going to another section first, so

Create an Array from a ListNode

Lets try to get this

const list = { value: 1, next: { value: 2, next: null } }
createArrayFromListNode(list)
// [ 1 ,2 ]

Lets define createArrayFromListNode(list: ListNode): string [] | number[]

const createArrayFromList = (list: ListNode): number[] | string[] => {
    let arr: any[] = []

    const createArray = (list: ListNode): string[] | number[] => {
        arr.push(list.value)
        if (list.next === null) {
           return arr
        } else {
            return createArray(list.next)
        }
    }

    return createArray(list)
}

Zip take 2

Now with our master function that gerudo guy won't take a chan.... we can do zip.

Lets try to get this

const list1 = { value: '1', next: {value: '2', next: null }}
const list2 = { value: 'a', next: {value: 'b', next: null }}
zip(list1, list2) 
// { value: '1a', next: { value: '2b', next: null } }

Lets define that zip(list1:ListNode, list2:ListNode): ListNode

const zip = (l1: ListNode, l2: ListNode) => {
    let arr1 = createArrayFromList(l1)
    let arr2 = createArrayFromList(l2)

    const zipListNode = (arr1: string[], arr2: string[]): string[] => {
        const arrZipped: string[] = []
        arr1.map((item: string, index: number) => {
            arrZipped.push(item+arr2[index])
        })
        return arrZipped
    }
    return zipListNode(arr1 as string[], arr2 as string[])
}

This is the secret for feeling productive on a Sunday cheesebags

We have

• Types✅
• Recursion✅
• Any ❌

Like any other codebase in production,
Hope you have a good week!

Jesus Cova is me and I like TypeScript and functional code.
I also use React, Next.js, and AWS-Amplify.

Twitter