CODEWITHSUNDEEP
swiftfunctional-programming
Senseful
Senseful

Reputation: 91891

Is there a high-order function to convert a linked list to an array?

Imagine I have a simple linked list:

class Node {
  var parent: Node?
}


// Create the chain: a <- b <- c
let a = Node()
let b = Node(parent: a)
let c = Node(parent: b)

Now I want to convert c into an array ([c, b, a]) so I can use other high-order functions like map.

What is a method that produces an array from a linked list typically called?

Is there a way to use other high-order functions to implement this and not use a loop?

The only implementation I could think of falls back to using a loop:

func chain<T>(_ initial: T, _ next: (T) -> T?) -> [T] {
  var result = [initial]
  while let n = next(result.last!) {
    result.append(n)
  }
  return result
}

chain(c) { $0.parent } // == [c, b, a]

I'm wondering if there is a built-in way to use functions like map/reduce/etc. to get the same results.

Upvotes: 2

Views: 230

Answers (2)

Cristik
Cristik

Reputation: 32870

You could make Node be a "denaturated" sequence, this will automatically bring all high-order functions: map, filter, reduce, flatMap, etc.

class Node {
    var parent: Node?
    var value: String
    
    init(parent: Node? = nil, value: String = "") {
        self.parent = parent
        self.value = value
    }
    
}

extension Node: Sequence {
    struct NodeIterator: IteratorProtocol {
        var node: Node?
        
        mutating func next() -> Node? {
            let result = node
            node = node?.parent
            return result
        }
    }
    
    func makeIterator() -> NodeIterator {
        NodeIterator(node: self)
    }
}


// Create the chain: a <- b <- c
let a = Node(value: "a")
let b = Node(parent: a, value: "b")
let c = Node(parent: b, value: "c")

// each node behaves like its own sequence
print(c.map { $0.value }) // ["c", "b", "a"]

print(b.map { $0.value }) // ["b", "a"]

Upvotes: 2

vacawama
vacawama

Reputation: 154691

You can use sequence(first:next:) to make a Sequence and then Array() to turn that sequence into an array:

let result = Array(sequence(first: c, next: { $0.parent }))

or equivalently:

let result = Array(sequence(first: c, next: \.parent))

You could use it to implement chain:

func chain<T>(_ initial: T, _ next: @escaping (T) -> T?) -> [T] {
    Array(sequence(first: initial, next: next))
}

But I'd just use it directly.

Note: If you just want to call map, you don't need to turn the sequence into an Array. You can just apply .map to the sequence.

For example, here is a useless map that represents each node in the linked list with a 1:

let result = sequence(first: c, next: \.parent).map { _ in 1 }

Upvotes: 2

Related Questions