Extracting objects in Array using functional programming

Question

I have some trouble to extract the data from a list of objects, i am learning functional programming concepts.

struct Country {
   let name: String
}

let country1 = Country(name: "Algeria")
let country2 = Country(name: "Angola")
let country3 = Country(name: "Belgium")

let countries = [country1, country2, country3]

What i want to do is a dictionary with the key the first character and the value is the list of all the countries witch begin with this character. In my example i will get:

let dic = ["A": [country1, country2], "B":[country3]]

I know how to do it with the "ugly" for loops. Like this:

  for country in countries {
     let first = country.name.first
     if !sections.keys.contains(first) {
        let matchedCountries = countries.filter {$0.name.hasPrefix(first)}
        sections[first] = matchedCountries
     }
  }

My question is: Is there an easy way to do it with a more functional manner ?

Would you like guidance on figuring it out yourself, or just the solution itself? — Alexander
– Alexander, Commented May 19, 2016 at 21:28
As you like, i think that i can use the reduce function with the filter one but for know dont see how :) — samir
– samir, Commented May 19, 2016 at 21:33

dfrib · Accepted Answer · 2016-05-19 21:51:15Z

2

I don't believe that for loops are to be avoided at all costs (and I personally wouldn't resort to name-calling the for ... in loops as "ugly" :), in some cases they might be the most appropriate construct. That said, you could use .forEach on your countries array (which is, though, in essence a for ... in loop) and simply append countries to existing keys and create new key-value pairs for non-existant ones (String:[Country] key-value pairs). E.g.:

/* your example above */
struct Country {
   let name: String
}

let country1 = Country(name: "Algeria")
let country2 = Country(name: "Angola")
let country3 = Country(name: "Belgium")

let countries = [country1, country2, country3]

/* .forEach solution */
var countryDict: [String: [Country]] = [:]
countries.forEach {
    if let first = $0.name.characters.first,
        case let key = String(first) {
        if let val = countryDict.removeValueForKey(key) {
            countryDict[key] = val+[$0]
        }
        else {
            countryDict[key] = [$0]
        }
    }
}

print(countryDict)
/* ["B": [Country(name: "Belgium")], 
    "A": [Country(name: "Algeria"), Country(name: "Angola")]] */

Note that one possible upside of this method is that you don't use loop-like constructs nested within the outer for loop (e.g. .contains and .filter); you only need to process each country in the countries array once.

edited May 19, 2016 at 21:51

answered May 19, 2016 at 21:43

dfrib

73.6k12 gold badges138 silver badges201 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Patrick Goley Over a year ago

I don't think it's that for loops are "bad", but they (and your example) require the creation of a mutable variable which is discouraged in functional programming, and not necessary with the reduce solution above.

MirekE Over a year ago

@Patrick Goley Well, you either create mutable dictionary or you recreate the dictionary every time you add an element to it. The reduce passes the first parameter (dictionary) as a let constant, so the reduce version may look cleaner from functional programming viewpoint, but apparently runs in quadratic time.

Carter · Accepted Answer · 2016-05-19 22:16:14Z

1

You can do this using by reducing countries to a dictionary of arrays by starting with a blank dictionary, using each countries letter as a key, and appending the country on each reduction.

Not on a Mac right now, but here's a Swift-pseudo-code approximation of how this would look:

let dicFinal = countries.reduce([:]) {
    dic, country in
    let letter = country.name[0]
    if let arr = dic[letter] {
        dic[letter] = arr + country
    } else {
        dic[letter] = [country]
    }
    return dic
}

edited May 19, 2016 at 22:16

answered May 19, 2016 at 22:02

Carter

3,0931 gold badge19 silver badges22 bronze badges

2 Comments

Patrick Goley Over a year ago

I'm not sure OP would be happy that you took his code from O(N) to O(N^2), at least without mentioning it. The map call isn't necessary (or valid, I think you forgot $0.name[0]), you could do that work in the reduce block and remove a factor of N.

Carter Over a year ago

Good point on the map call being unnecessary, updating now :)

Alexander · Accepted Answer · 2016-05-20 01:20:00Z

Here is my solution:

public struct Country : CustomStringConvertible {
    let name: String
    public var description : String {
        get {
            return name
        }
    }
}

var countries = [
    Country(name: "Algeria"),
    Country(name: "Belgium"),
    Country(name: "Angola"),
    Country(name: "Canada"),
    Country(name: "Brazil"),
    Country(name: "Denmark"),
]

let AlphabetizedCountries = countries
    .sort{$0.name < $1.name}
    .reduce([String : [Country]]()) {
        var dict = $0
        let firstLetter = String($1.name.characters.first!)
        dict[firstLetter] = (dict[firstLetter] ?? []) + [$1]
        return dict
    }

print(AlphabetizedCountries)

Output: ["B": [Belgium, Brazil], "A": [Algeria, Angola], "C": [Canada], "D": [Denmark]]

The countries will be sorted within their letter's array, but the letter arrays themselves won't be sorted in the dictionary, as dictionaries don't preserve ordering.

This code is O(NlogN) if you include the sort, O(logN) if you don't. But as is characteristic with most functional programming, this solution would be quite inefficient compared to its for loop counterpart (unless the compiler is exceptionally good at optimizing away all the redundant copying).

Collectives™ on Stack Overflow

Extracting objects in Array using functional programming

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related