Возвращает список узлов, которые находятся на расстоянии k шагов от заданного узла в графе, используя f #

Question

Я пытаюсь сделать это упражнение: У меня уже есть первая часть:

let rec makeRoadMap (data:(string * string list) list) = 
    match data with
    | []-> Map.empty
    | ah::at-> (makeRoadMap at).Add(fst ah, setOfDestinations (snd ah))

Я пытаюсь завершить эту функцию:

let upToManySteps (map:RoadMap) (n: int) (startCity : Destination)=

, который возвращает набор городов, которые находятся на расстоянии n шагов от стартового города. Моя идея состоит в том, чтобы рекурсивно вызвать метод, чтобы перебрать расстояние n. Но я застрял, пожалуйста, помогите мне найти способ сделать это.

Answer 1

Вот пример, чтобы показать, как вы можете напрямую декомпозировать кортеж, используя шаблоны в аргументах лямбда-функции, как вы можете использовать дискриминаторы (City, Roads) в качестве функций и как использовать конвейерную обработку, чтобы код можно было прочитать как алгоритм .

• Из данных
• Сопоставить каждый (строка * список строк) кортеж из списка с (City, Set) кортежем
• Конвертировать полученный список в набор
• Конвертировать полученный набор в RoadMap

(строка * список строк) список -> RoadMap

let MakeRoadMap data =
    data 
    |> List.map (fun (str, lst) -> (City str, lst |> List.map City |> Set.ofList))
    |> Map.ofList
    |> Roads

Мы также могли использовать оператор композиции функций и не указывать аргумент функции, тип которого может быть выведен.

let makeRoadMap =
    List.map (fun (str, lst) -> (City str, lst |> List.map City |> Set.ofList))
    >> Map.ofList
    >> Roads

То же самое для функции upToManySteps

let rec upToManySteps roadMap steps city =
    match roadMap, steps with
    | _, n when n < 0 -> invalidArg "steps" "Must be positive"
    | _, 0            -> Set.empty |> Set.add city
    | Roads map, 1    -> map |> Map.find city
    | Roads map, n    -> map 
                         |> Map.find city  
                         |> Seq.map (fun x -> upToManySteps roadMap (steps - 1) x)
                         |> Set.unionMany

Answer 2

В дополнение к тому, что я сказал в комментарии, для второй части следует также обратить внимание на тип Set <'T> и функции Set * .

Для второй части вашего упражнения, например, взять «Андуло» в качестве стартового города.

Если количество шагов равно 1, вы просто возвращаете «значение» клавиши «Andulo» в RoadMap (set [City "Bibala"; City "Cacolo"; City "Dondo"]).

Если количество шагов равно 2, вы должны вернуть объединение значений клавиш "Bibala", "Cacolo" и "Dondo" (т.е. объединение set [City "Andulo"; City "Dondo"; City "Galo"], set [City "Andulo"; City "Dondo"] и set [City "Andulo"; City "Bibala"; City "Cacolo"; City "Ekunha"; City "Funda"], что : set [City "Andulo"; City "Bibala"; City "Cacolo"; City "Dondo"; City "Ekunha"; City "Funda"; City "Galo"].

Итак, функции, необходимые для построения рекурсивной функции в соответствии с верхними примерами: Set.map (или Seq.map) и Set.unionMany.