sample trie (Chapter 9) about functional-swift HOT 11 CLOSED

Hi @sstadelman

Thanks for the question! In truth, we still get some weird SourceKit crashes when you try to build theses structures -- that's one reason why we haven't included many examples in the book yet.

To give you some idea, here's how to construct a trie storing a single character:

func single<T:Hashable> (x : T) -> Trie<T> {
    let leaf = Trie.Make(true,[T: Trie<T>]())
    return Trie.Make(false, [x : leaf])
}


// We can use this to build the following trie, storing "cat" and "cab"
//      /--t
// -c-a-
//      \--b


// Here are two tries storing "t" and "b"
let onlyT : Trie<Character> = single("t")
let onlyB : Trie<Character> = single("b")
// We can but them together, to create the trie storing "t" and "b"
let subtree2 : Trie<Character> = Trie.Make(false, ["t" : onlyT, "b" : onlyB])
// Which we can extend to the trie storing "ab" and "at"
let subtree1 : Trie<Character> = Trie.Make(false, ["a" : subtree2])
// Which we can extend to the trie storing "cab" and "cat"
let root : Trie<Character> = Trie.Make(false, ["c" : subtree1])

Hope this helps!

from functional-swift.

@wouter-swierstra Thanks, this is really helpful!

from functional-swift.

@wouter-swierstra question regarding the Trie chapter as well. How would you go about calling empty?

func empty<T: Hashable>() -> Trie<T> {
  return Trie.Make(false, [T: Trie<T>]())
}

Since you're not passing in an attribute I'm guessing that you're left with no choice but to do this?

var empty: Trie<Character> = empty()

from functional-swift.

@csgavino Yes -- that's how you'd need to create an empty trie.

I seem to remember that you can't define empty as constant (using let rather than func) because Swift doesn't like generics in let-bound values.

from functional-swift.

@wouter-swierstra I have tried "cat", "cab" trie above. If I try to get elements of trie and print them this is what i get:

I think problem is here:
let onlyT : Trie<Character> = single("t")

This function returns trie which already has key "t". After that new trie is created and "t" key is added again:
let subtree2 : Trie<Character> = Trie.Make(false, ["t" : onlyT, "b" : onlyB])

Am I missing something here maybe?

from functional-swift.

@jcavar You're right of course. The obvious fix is to define a fix storing only the empty string, and associate this with the "t" and "b" keys in subtree2:

func emptyString<T: Hashable>() -> Trie<T> {
  return Trie.Make(true, [T: Trie<T>]())
}
let subtree2 : Trie<Character> = Trie.Make(false, ["t" : emptyString(), "b" : emptyString()])

from functional-swift.

Yes, I see. But in this way emptyString contradicts to this statement from book:
“If we had chosen to set the boolean stored in the empty trie to true rather than false, the empty string would be a member of the empty trie — which is probably not the behavior that we want.”

For example we could do this:
let trie = emptyString()
and we have empty string part of trie.

from functional-swift.

@jcavar -- yes but in this example, we want to have the empty string in the trie. I've tried to create a crappy ASCII art visualization of the situation, decorating every node in the trie with 0 (not a member, false) and 1 (is a member, true):

// We can use this to build the following trie, storing "cat" and "cab"
//                   /--(0,t) -- (1,"")
// -(0,c)-(0,a)-
//                   \--(0,b) -- (1,"")

Reading from left to right, "", "c" ,"ca" are all not in the trie, but "cat" and "cab" are. Does this make sense?

from functional-swift.

Yes, you are right. Thanks :)

from functional-swift.

I finally understood that order establish an end to a "word", the trie's children must have at least one trie who's isElem set to true. So it does make sense that the empty function returns a trie such as this. Then the single function should just create a trie who's children are empty as well.

func empty<T : Hashable>()->Trie<T> {
    return Trie(isElem:true, children:[T:Trie<T>]())
}

func single<T : Hashable>(t:T)->Trie<T> {
    return Trie(isElem:false, children:[t:empty()])
}  

This was a great chapter and with the help from above I elaborated on the example and made a function to add an array to an existing trie while maintaining its child relationships. Thanks for the help guys and great book @wouter-swierstra.

func create<T: Hashable>(t:[T])->Trie<T> {
    let trie = t.reverse().reduce(empty()) { tr, next in
        return Trie.Make(false, children:[next:tr])
    }
    return trie
}

func addTo<T: Hashable>(t:[T], trie:Trie<T>)->Trie<T> {
    if let (head, tail) = t.decompose {
        var children                = trie.children
        var trieToReturn:Trie<T>!
        if let subTrie = children[head] {
            if tail.count > 0 {
                // keep drilling down till you hit the last of the array 
                // or have to create the new trie
                trieToReturn = addTo(tail, subTrie)
            } else {
                // its the last in the array, 
                // create trie with isElem true and add it to the children
                trieToReturn = Trie.Make(true, children:subTrie.children)
            }
        } else {
            // head is not a part of the trie,
            // create its own and to tri children
            trieToReturn = create(tail)
        }
        // return trie with adjusted children and copy isElem
        children[head] = trieToReturn
        return Trie.Make(trie.isElem, children:children)
    } else {
        return trie
    }
}

func wordToStringArray(word:String)->[String] {
    return Array(word).map { c in String(c) }
}

let beard               = wordToStringArray("beard")
let bear                = wordToStringArray("bear")
let beer                = wordToStringArray("beer")
let beet                = wordToStringArray("beet")
let beef                = wordToStringArray("beef")
let be                  = wordToStringArray("be")
let golf                = wordToStringArray("golf")

var completionList:Trie<String>!
completionList          = create(be)
completionList          = addTo(beard, completionList)
completionList          = addTo(bear, completionList)
completionList          = addTo(be, completionList)
completionList          = addTo(beer, completionList)
completionList          = addTo(beef, completionList)
elements(completionList)

let test                = wordToStringArray("b")
let ac                  = autoComplete(test, completionList)//.map { c in c.reduce("") { f,n in f + n } }

from functional-swift.

Thanks @hatebyte! I recently added a very similar function to this chapter (should be in the next update we release). I've had some issues with the addTo functions triggering Swift bugs in the past; I'll check whether this is fixed in the latest version. Ideally, I'd like to include a small demo/playground with the chapter to help visualise how tries are built and searched.

from functional-swift.