Sorting anything with Execute AppleScript actions

[ComplexPoint]

Applescript seems, at first sight, to be rather poorly equipped for sorting:

1. It lacks the fast and flexible built-in array sorts of JavaScript (see Sorting anything with Execute JavaScript actions )
2. Home-made sort handlers are certainly possible, but take some work, and may not scale or perform very well.
3. Even if we install the Satimage 3rd party library, its flexibility turns out to be limited - we can’t for example, sort a list of records by particular keys, or by functions of more than one key, or sort simple values by derived properties like the length of strings, or their final rather than initial letters.

We do, however have access to some useful speed and flexibility through the interface to ObjC NSArray sorting methods.

Here is a sortOn(f, boolUp, xs) function which takes, (reading the arguments right to left):

1. xs a list of records, lists or simple atomic AppleScript values
2. boolUp (true for ascending sorts, false for descending)
3. f a function which takes as input an item of whatever type of data the list contains, and returns some orderable value (number, string, date) derived from such an item.

A simple example of f if we wanted to sort a list of words by their length rather than their lexical order would be:

-- stringLength :: String -> Int
on stringLength(item)
    length of item
end

Draft AppleScript source for sortOn, with some examples of sorting strings and records by derived or default properties

(Note that it requires the incantation

use framework "Foundation"
use scripting additions

and a couple of generic helper functions also listed below – map and mReturn).

NB (Version 0.2 in a later post in this thread has a different argument pattern, and is more flexible)

use framework "Foundation"
use scripting additions


-- SORT ON ANY PROPERTY (VALUES OF RECORD KEYS, 
-- STRING LENGTH, DERIVED PROPERTIES)

-- sortOn :: Ord b => (a -> b) -> Bool -> [a] -> [a]
on sortOn(f, boolUp, xs)
    set ca to current application
    script dec
        property g : mReturn(f)
        on |λ|(x)
            set nsDct to (ca's NSMutableDictionary's ¬
                dictionaryWithDictionary:{a:g's |λ|(x)})
            nsDct's setValue:x forKey:("b")
            nsDct
        end |λ|
    end script
    
    script undec
        on |λ|(x)
            b of x
        end |λ|
    end script
    
    map(undec, ((ca's NSArray's arrayWithArray:map(dec, xs))'s ¬
        sortedArrayUsingDescriptors:{ca's NSSortDescriptor's ¬
            sortDescriptorWithKey:"a" ascending:boolUp}) as list)
end sortOn

-- TESTS ------------------------------------------------------------------
-- cityData :: () -> [Record]
on cityData()
    {{city:"Shanghai", pop:24.3, country:"China", capital:false}, ¬
        {city:"Beijing", pop:21.5, country:"China", capital:true}, ¬
        {city:"Delhi", pop:11.0, country:"India", capital:true}, ¬
        {city:"Lagos", pop:16.0, country:"Nigeria", capital:true}, ¬
        {city:"Karachi", pop:14.9, country:"Pakistan", capital:false}, ¬
        {city:"Dhaka", pop:14.5, country:"Bangladesh", capital:true}, ¬
        {city:"Guangzhou", pop:14.0, country:"China", capital:false}, ¬
        {city:"Istanbul", pop:14.0, country:"Turkey", capital:false}, ¬
        {city:"Tokyo", pop:13.5, country:"Japan", capital:true}}
end cityData

-- population :: Record -> Real
on population(x)
    pop of x
end population

-- country :: Record -> String
on country(x)
    country of x
end country

-- greekAlphabet :: () -> [String]
on greekAlphabet()
    ["alpha", "beta", "gamma", "delta", "epsilon", "zeta", ¬
        "eta", "theta", "iota", "kappa", "lambda", "mu"]
end greekAlphabet

-- stringLength :: String -> Int
on stringLength(s)
    length of s
end stringLength

-- romanAlpha :: String -> String
on romanAlpha(x)
    x
end romanAlpha

on run
    sortOn(stringLength, true, greekAlphabet())
    
    --> {"mu", "eta", "beta", "zeta", "iota", "alpha", "gamma", 
    --  "delta", "theta", "kappa", "lambda", "epsilon"}
    
    sortOn(stringLength, false, greekAlphabet())
    
    --> {"epsilon", "lambda", "alpha", "gamma", "delta", "theta", 
    --   "kappa", "beta", "zeta", "iota", "eta", "mu"}
    
    sortOn(romanAlpha, true, greekAlphabet())
    
    --> {"alpha", "beta", "delta", "epsilon", "eta", "gamma", 
    --   "iota", "kappa", "lambda", "mu", "theta", "zeta"}
    
    sortOn(romanAlpha, false, greekAlphabet())
    
    --> {"zeta", "theta", "mu", "lambda", "kappa", "iota", 
    --   "gamma", "eta", "epsilon", "delta", "beta", "alpha"}
    
    sortOn(population, true, cityData())
    
    --> {{capital:true, country:"India", city:"Delhi", pop:11.0}, 
    -- {capital:true, country:"Japan", city:"Tokyo", pop:13.5}, 
    -- {capital:false, country:"China", city:"Guangzhou", pop:14.0}, 
    -- {capital:false, country:"Turkey", city:"Istanbul", pop:14.0}, 
    -- {capital:true, country:"Bangladesh", city:"Dhaka", pop:14.5}, 
    -- {capital:false, country:"Pakistan", city:"Karachi", pop:14.9}, 
    -- {capital:true, country:"Nigeria", city:"Lagos", pop:16.0}, 
    -- {capital:true, country:"China", city:"Beijing", pop:21.5}, 
    -- {capital:false, country:"China", city:"Shanghai", pop:24.3}}
    
    sortOn(population, false, cityData())
    
    --> {{capital:false, country:"China", city:"Shanghai", pop:24.3}, 
    -- {capital:true, country:"China", city:"Beijing", pop:21.5}, 
    -- {capital:true, country:"Nigeria", city:"Lagos", pop:16.0}, 
    -- {capital:false, country:"Pakistan", city:"Karachi", pop:14.9}, 
    -- {capital:true, country:"Bangladesh", city:"Dhaka", pop:14.5}, 
    -- {capital:false, country:"China", city:"Guangzhou", pop:14.0}, 
    -- {capital:false, country:"Turkey", city:"Istanbul", pop:14.0}, 
    -- {capital:true, country:"Japan", city:"Tokyo", pop:13.5}, 
    -- {capital:true, country:"India", city:"Delhi", pop:11.0}}
    
    sortOn(country, true, cityData())
    
    --> {{capital:true, country:"Bangladesh", city:"Dhaka", pop:14.5}, 
    -- {capital:false, country:"China", city:"Shanghai", pop:24.3}, 
    -- {capital:true, country:"China", city:"Beijing", pop:21.5}, 
    -- {capital:false, country:"China", city:"Guangzhou", pop:14.0}, 
    -- {capital:true, country:"India", city:"Delhi", pop:11.0}, 
    -- {capital:true, country:"Japan", city:"Tokyo", pop:13.5}, 
    -- {capital:true, country:"Nigeria", city:"Lagos", pop:16.0}, 
    -- {capital:false, country:"Pakistan", city:"Karachi", pop:14.9}, 
    -- {capital:false, country:"Turkey", city:"Istanbul", pop:14.0}}
end run


-- GENERIC FUNCTIONS ---------------------------------------------------------

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

[JMichaelTX]

@ComplexPoint

Here is a sortOn(f, boolUp, xs) function which takes, (reading the arguments right to left):

1. xs a list of records, lists or simple atomic AppleScript values

• boolUp (true for ascending sorts, false for descending)
• f a function which takes as input an item of whatever type of data the list contains, and returns some orderable value (number, string, date) derived from such an item

@ComplexPoint, thanks for sharing this. It is very impressive!

It is indeed very nice to have one sort function that will handle both lists and records, and the flexibility to define a function to specify the sort key.

Your sample dataset ran very fast, only 0.02 sec in Script Debugger 6.0.5 (6A205) on macOS 10.11.6.

I'm wondering if you have tested it with larger datasets, say 1,000+ list items or records?

Also, I wonder if it can sort on multiple keys, with each key sort direction specified separately? That would be very powerful.

Finally, thanks for defining the sort parameters in plain English that is easy to understand.

[ComplexPoint]

larger datasets, say 1,000+ list items or records

Well, perhaps worth trying, though Applescript memory allocations are quite constrained. AppleScript makes a serviceable penknife for a picnic or lunch-break, but after a few hundred records I would personally be reaching for a different instrument.

multiple keys, with each key sort direction specified separately

A modified function below with slightly different arguments, ( and one additional generic helper function –unzip )

sortOn(f, xs) has two arguments – reading from right to left:

1. xs a list of items to be sorted. (The items can be records, lists, or simple values).
2. f a single function – an Applescript handler of type (Item -> simple orderable value),
   or a list of such functions.
   • If the f argument is a list, any function in it can optionally be followed by a Bool.
     (false means descending sort).
   • Any subgrouping {sub-bracketing} in the list is optional and ignored.
   • The sequence of key functions and optional direction bools defines primary to N-ary sort keys.

The examples below are the same as before with the exception of the last.

The last example sorts by primary, secondary and tertiary keys:

sortOn({country, {capital, false}, {population, false}}, cityData())

1. The primary key (ascending String) is the name of the country, so Bangladesh comes first, followed by three records in which the country is China
2. the secondary key is a boolean value for capital (descending Bool, true before false) so Beijing, which is the capital of China, comes before Shanghai and Guangzhou
3. the tertiary key is population (descending Real), so Shanghai, with a larger population, comes before Guangzhou.

use framework "Foundation"
use scripting additions

-- Ver 0.2 Rob Trew 2017

-- SORT ON ANY PROPERTY (VALUES OF RECORD KEYS, 
-- STRING LENGTH, DERIVED PROPERTIES)

-- ARGUMENTS:

--    xs:  List of items to be sorted. 
--          (The items can be records, lists, or simple values).
--
--    f:    A single (a -> b) function (Applescript handler),
--          or a list of such functions.
--          if the argument is a list, any function can 
--          optionally be followed by a bool. 
--          (False -> descending sort)
--
--          (Subgrouping in the list is optional and ignored)
--          Each function (Item -> Value) in the list should 
--          take an item (of the type contained by xs) 
--          as its input and return a simple orderable value 
--          (Number, String, or Date).
--
--          The sequence of key functions and optional 
--          direction bools defines primary to N-ary sort keys.

-- sortOn :: Ord b => ((a -> b) | [((a -> b), Bool)])  -> [a] -> [a]
on sortOn(f, xs)
    script keyBool
        on |λ|(x, a)
            if class of x is boolean then
                {asc:x, fbs:fbs of a}
            else
                {asc:true, fbs:({{x, asc of a}} & fbs of a)}
            end if
        end |λ|
    end script
    set {fs, bs} to unzip(fbs of foldr(keyBool, ¬
        {asc:true, fbs:{}}, flatten({f})))
    
    set intKeys to length of fs
    set ca to current application
    script dec
        property gs : map(my mReturn, fs)
        on |λ|(x)
            set nsDct to (ca's NSMutableDictionary's ¬
                dictionaryWithDictionary:{val:x})
            repeat with i from 1 to intKeys
                (nsDct's setValue:((item i of gs)'s |λ|(x)) ¬
                    forKey:(character id (96 + i)))
            end repeat
            nsDct as record
        end |λ|
    end script
    
    script descrip
        on |λ|(bool, i)
            ca's NSSortDescriptor's ¬
                sortDescriptorWithKey:(character id (96 + i)) ¬
                    ascending:bool
        end |λ|
    end script
    
    script undec
        on |λ|(x)
            val of x
        end |λ|
    end script
    
    map(undec, ((ca's NSArray's arrayWithArray:map(dec, xs))'s ¬
        sortedArrayUsingDescriptors:map(descrip, bs)) as list)
end sortOn


-- TESTS ------------------------------------------------------------------
-- cityData :: () -> [Record]
on cityData()
    {{city:"Shanghai", pop:24.3, country:"China", capital:false}, ¬
        {city:"Beijing", pop:21.5, country:"China", capital:true}, ¬
        {city:"Delhi", pop:11.0, country:"India", capital:true}, ¬
        {city:"Lagos", pop:16.0, country:"Nigeria", capital:true}, ¬
        {city:"Karachi", pop:14.9, country:"Pakistan", capital:false}, ¬
        {city:"Dhaka", pop:14.5, country:"Bangladesh", capital:true}, ¬
        {city:"Guangzhou", pop:14.0, country:"China", capital:false}, ¬
        {city:"Istanbul", pop:14.0, country:"Turkey", capital:false}, ¬
        {city:"Tokyo", pop:13.5, country:"Japan", capital:true}}
end cityData

-- population :: Record -> Real
on population(x)
    pop of x
end population

-- country :: Record -> String
on country(x)
    country of x
end country

-- capital :: Record -> Bool
on capital(x)
    capital of x
end capital

-- greekAlphabet :: () -> [String]
on greekAlphabet()
    ["alpha", "beta", "gamma", "delta", "epsilon", "zeta", ¬
        "eta", "theta", "iota", "kappa", "lambda", "mu"]
end greekAlphabet

-- stringLength :: String -> Int
on stringLength(s)
    length of s
end stringLength

-- romanAlpha :: String -> String
on romanAlpha(x)
    x
end romanAlpha

on run
    
    sortOn(stringLength, greekAlphabet())
    
    --> {"mu", "eta", "beta", "zeta", "iota", "alpha", "gamma", 
    --  "delta", "theta", "kappa", "lambda", "epsilon"}
    
    sortOn({stringLength, false}, greekAlphabet())
    
    --> {"epsilon", "lambda", "alpha", "gamma", "delta", "theta", 
    --   "kappa", "beta", "zeta", "iota", "eta", "mu"}
    
    sortOn(romanAlpha, greekAlphabet())
    
    --> {"alpha", "beta", "delta", "epsilon", "eta", "gamma", 
    --   "iota", "kappa", "lambda", "mu", "theta", "zeta"}
    
    sortOn({romanAlpha, false}, greekAlphabet())
    
    --> {"zeta", "theta", "mu", "lambda", "kappa", "iota", 
    --   "gamma", "eta", "epsilon", "delta", "beta", "alpha"}
    
    sortOn(population, cityData())
    
    --> {{capital:true, country:"India", city:"Delhi", pop:11.0}, 
    -- {capital:true, country:"Japan", city:"Tokyo", pop:13.5}, 
    -- {capital:false, country:"China", city:"Guangzhou", pop:14.0}, 
    -- {capital:false, country:"Turkey", city:"Istanbul", pop:14.0}, 
    -- {capital:true, country:"Bangladesh", city:"Dhaka", pop:14.5}, 
    -- {capital:false, country:"Pakistan", city:"Karachi", pop:14.9}, 
    -- {capital:true, country:"Nigeria", city:"Lagos", pop:16.0}, 
    -- {capital:true, country:"China", city:"Beijing", pop:21.5}, 
    -- {capital:false, country:"China", city:"Shanghai", pop:24.3}}
    
    sortOn({population, false}, cityData())
    
    --> {{capital:false, country:"China", city:"Shanghai", pop:24.3}, 
    -- {capital:true, country:"China", city:"Beijing", pop:21.5}, 
    -- {capital:true, country:"Nigeria", city:"Lagos", pop:16.0}, 
    -- {capital:false, country:"Pakistan", city:"Karachi", pop:14.9}, 
    -- {capital:true, country:"Bangladesh", city:"Dhaka", pop:14.5}, 
    -- {capital:false, country:"China", city:"Guangzhou", pop:14.0}, 
    -- {capital:false, country:"Turkey", city:"Istanbul", pop:14.0}, 
    -- {capital:true, country:"Japan", city:"Tokyo", pop:13.5}, 
    -- {capital:true, country:"India", city:"Delhi", pop:11.0}}
    
    sortOn(country, cityData())
    
    --> {{capital:true, country:"Bangladesh", city:"Dhaka", pop:14.5}, 
    -- {capital:false, country:"China", city:"Shanghai", pop:24.3}, 
    -- {capital:true, country:"China", city:"Beijing", pop:21.5}, 
    -- {capital:false, country:"China", city:"Guangzhou", pop:14.0}, 
    -- {capital:true, country:"India", city:"Delhi", pop:11.0}, 
    -- {capital:true, country:"Japan", city:"Tokyo", pop:13.5}, 
    -- {capital:true, country:"Nigeria", city:"Lagos", pop:16.0}, 
    -- {capital:false, country:"Pakistan", city:"Karachi", pop:14.9}, 
    -- {capital:false, country:"Turkey", city:"Istanbul", pop:14.0}}
    
    sortOn({country, {capital, false}, {population, false}}, cityData())
    
    --> {{capital:true, country:"Bangladesh", city:"Dhaka", pop:14.5}, 
    -- {capital:true, country:"China", city:"Beijing", pop:21.5}, 
    -- {capital:false, country:"China", city:"Shanghai", pop:24.3}, 
    -- {capital:false, country:"China", city:"Guangzhou", pop:14.0}, 
    -- {capital:true, country:"India", city:"Delhi", pop:11.0}, 
    -- {capital:true, country:"Japan", city:"Tokyo", pop:13.5}, 
    -- {capital:true, country:"Nigeria", city:"Lagos", pop:16.0}, 
    -- {capital:false, country:"Pakistan", city:"Karachi", pop:14.9}, 
    -- {capital:false, country:"Turkey", city:"Istanbul", pop:14.0}}
end run


-- GENERIC FUNCTIONS ---------------------------------------------------------

-- concatMap :: (a -> [b]) -> [a] -> [b]
on concatMap(f, xs)
    set acc to {}
    tell mReturn(f)
        repeat with x in xs
            set acc to acc & |λ|(contents of x)
        end repeat
    end tell
    return acc
end concatMap

-- flatten :: Tree a -> [a]
on flatten(t)
    if class of t is list then
        my concatMap(my flatten, t)
    else
        t
    end if
end flatten

-- foldr :: (a -> b -> b) -> b -> [a] -> b
on foldr(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from lng to 1 by -1
            set v to |λ|(item i of xs, v, i, xs)
        end repeat
        return v
    end tell
end foldr

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

-- unzip :: [(a,b)] -> ([a],[b])
on unzip(xys)
    set xs to {}
    set ys to {}
    repeat with xy in xys
        set {x, y} to xy
        set end of xs to x
        set end of ys to y
    end repeat
    return {xs, ys}
end unzip

[JMichaelTX]

@ComplexPoint

A modified function below with slightly different arguments, ( and one additional generic helper function –unzip )

sortOnFnBools(fnBools, xs) has two arguments

Thanks, @ComplexPoint, that looks great!

[ComplexPoint]

Ver 2 of the N-ary sort function above is now redefined as sortOn(f, xs)

The argument f which defines the sort can now be either:

1. A single function (Applescript handler), or
2. A ordered list of such key functions, in which any key function can optionally be followed by a sort-direction Bool

(false specifies descending sort for the immediately preceding key function – in the absence of a Bool, the default direction is ascending)

If f is a list, bracketing a key function with an accompanying bool as a 2-member sub-list is optional and ignored.

---

Note:

• sortOn(f, xs) still requires the use framework "Foundation" and use scripting additions incantations at the top of the script, and
• it also requires inclusion of the following generic helper functions – concatMap, flatten, foldr, map, mReturn, unzip

[ComplexPoint]

Another example – lexical sorts from right to left

Sorting from the suffixes towards the prefixes (either ascending or descending)

use framework "Foundation"
use scripting additions

-- greekLetterNames :: () -> [String]
on greekLetterNames()
    {"alpha", "beta", "gamma", "delta", "epsilon", "zeta", "eta", ¬
        "theta", "iota", "kappa", "lambda", "mu"}
end greekLetterNames

-- reversedString :: String -> String
on reversedString(x)
    (reverse of characters of x) as string
end reversedString

on run
    -- Lexical sorts from right to left
    
    -- From -da up to  -mu, 
    
    sortOn(reversedString, greekLetterNames())
    
    --> {"lambda", "alpha", "gamma", "kappa", "eta", "beta", 
    --         "theta", "zeta", "delta", "iota", "epsilon", "mu"}
    
    
    -- and from -mu down to -da.
    
    sortOn({reversedString, false}, greekLetterNames())
    
    --> {"mu", "epsilon", "iota", "delta", "zeta", "theta", 
    --        "beta", "eta", "kappa", "gamma", "alpha", "lambda"}
    
    
end run

-- sortOn ------------------------------------------------------------------

-- sortOn :: Ord b => ((a -> b) | [((a -> b), Bool)])  -> [a] -> [a]
on sortOn(f, xs)
    script keyBool
        on |λ|(x, a)
            if class of x is boolean then
                {asc:x, fbs:fbs of a}
            else
                {asc:true, fbs:({{x, asc of a}} & fbs of a)}
            end if
        end |λ|
    end script
    set {fs, bs} to unzip(fbs of foldr(keyBool, ¬
        {asc:true, fbs:{}}, flatten({f})))
    
    set intKeys to length of fs
    set ca to current application
    script dec
        property gs : map(my mReturn, fs)
        on |λ|(x)
            set nsDct to (ca's NSMutableDictionary's ¬
                dictionaryWithDictionary:{val:x})
            repeat with i from 1 to intKeys
                (nsDct's setValue:((item i of gs)'s |λ|(x)) ¬
                    forKey:(character id (96 + i)))
            end repeat
            nsDct as record
        end |λ|
    end script
    
    script descrip
        on |λ|(bool, i)
            ca's NSSortDescriptor's ¬
                sortDescriptorWithKey:(character id (96 + i)) ¬
                    ascending:bool
        end |λ|
    end script
    
    script undec
        on |λ|(x)
            val of x
        end |λ|
    end script
    
    map(undec, ((ca's NSArray's arrayWithArray:map(dec, xs))'s ¬
        sortedArrayUsingDescriptors:map(descrip, bs)) as list)
end sortOn


-- GENERIC FUNCTIONS ---------------------------------------------------------

-- concatMap :: (a -> [b]) -> [a] -> [b]
on concatMap(f, xs)
    set acc to {}
    tell mReturn(f)
        repeat with x in xs
            set acc to acc & |λ|(contents of x)
        end repeat
    end tell
    return acc
end concatMap

-- flatten :: Tree a -> [a]
on flatten(t)
    if class of t is list then
        my concatMap(my flatten, t)
    else
        t
    end if
end flatten

-- foldr :: (a -> b -> b) -> b -> [a] -> b
on foldr(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from lng to 1 by -1
            set v to |λ|(item i of xs, v, i, xs)
        end repeat
        return v
    end tell
end foldr

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

-- unzip :: [(a,b)] -> ([a],[b])
on unzip(xys)
    set xs to {}
    set ys to {}
    repeat with xy in xys
        set {x, y} to xy
        set end of xs to x
        set end of ys to y
    end repeat
    return {xs, ys}
end unzip