Sort dependency graphs in Elm. Run this in Ellie: https://ellie-app.com/8NWh6CWDn3Sa1. Algorithm based on StackOverflow Answer: https://stackoverflow.com/a/54346588/6798201

topological-sort.elm

module Main exposing (main)

import Browser
import Html exposing (Html, button, div, h2, text)
import Html.Events exposing (onClick)
import Dict exposing (Dict)
import Set exposing (Set)


type alias Model =
    { }


initialModel : Model
initialModel =
    { }


type Msg
    = DoNothing


update : Msg -> Model -> Model
update msg model =
    model


view : Model -> Html Msg
view model =
    div []
        [ h2 [] [ text "Dependency graph" ]
        , text <| Debug.toString dependencies
        , h2 [] [ text "Sorted according to dependencies" ]
        , text <| Debug.toString <| sortDependencies dependencies
        ]


dependencies =
    Dict.fromList
        [ ("A", [])
        , ("B", ["A"])
        , ("C", ["A", "B"])
        , ("D", ["F"])
        , ("E", ["D", "C"])
        , ("F", [])
        , ("G", ["H"])
        , ("H", ["G"])
        ]


type alias Dep =
    Dict String (List String)


sortDependencies : Dep -> List String
sortDependencies dep =
    let
        (result, _, _) =
            sortDependenciesHelper ([], Set.empty, dep)
    in
    List.reverse result
    
    
sortDependenciesHelper : (List String, Set String, Dep) -> (List String, Set String, Dep)
sortDependenciesHelper (result0, used0, dep0) =
    let
        (result1, used1, dep1) =
            Dict.foldl
            (\k v (result, used, dep) ->
                if List.all (\value -> Set.member value used) v then
                    (k :: result, Set.insert k used, Dict.filter (\k1 _ -> k /= k1) dep)
                else
                    (result, used, dep)
            )
            (result0, used0, dep0)
            dep0
    in
    if Dict.isEmpty dep1 then
        (result1, used1, dep1)
    else if Dict.size dep0 == Dict.size dep1 then
        ((List.reverse <| Dict.keys dep1) ++ result1, used1, dep1)
    else
        sortDependenciesHelper (result1, used1, dep1)


main : Program () Model Msg
main =
    Browser.sandbox
        { init = initialModel
        , view = view
        , update = update
        }