Packages
search_algorithms_gleam

0.2.0
0.2.0 0.1.0
A collection of common Search Algorithms
HexDocs
Current section
Files
Jump to
Readme 2 Versions 4 Dependencies Dependants Files Activity
search_algorithms_gleam src search_algorithms.erl
Raw
src/search_algorithms.erl

-module(search_algorithms).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/search_algorithms.gleam").
-export([breadth_first/3, depth_first/3, dijkstra_assoc/3, dijkstra/4, a_star_assoc/4, a_star/5]).

-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.

-file("src/search_algorithms.gleam", 8).
?DOC(" Breadth First Search\n").
-spec breadth_first(fun((GKI) -> list(GKI)), fun((GKI) -> boolean()), GKI) -> {ok,
        list(GKI)} |
    {error, nil}.
breadth_first(Get_next_states, Is_found, Initial_state) ->
    _pipe@1 = internal@generalized_search:generalized_search(
        internal@search_container:new_queue(),
        fun gleam@function:identity/1,
        fun(_, _) -> false end,
        fun(Estimate_state_pair) ->
            _pipe = Get_next_states(erlang:element(2, Estimate_state_pair)),
            gleam@list:map(_pipe, fun(State) -> {0, State} end)
        end,
        fun(State@1) -> Is_found(erlang:element(2, State@1)) end,
        {0, Initial_state}
    ),
    gleam@result:map(
        _pipe@1,
        fun(List) ->
            gleam@list:map(List, fun(T) -> erlang:element(2, T) end)
        end
    ).

-file("src/search_algorithms.gleam", 28).
?DOC(" Depth First Search\n").
-spec depth_first(fun((GKN) -> list(GKN)), fun((GKN) -> boolean()), GKN) -> {ok,
        list(GKN)} |
    {error, nil}.
depth_first(Get_next_states, Is_found, Initial_state) ->
    _pipe@1 = internal@generalized_search:generalized_search(
        internal@search_container:new_stack(),
        fun gleam@function:identity/1,
        fun(_, _) -> true end,
        fun(State) -> _pipe = Get_next_states(erlang:element(2, State)),
            gleam@list:map(_pipe, fun(State@1) -> {0, State@1} end) end,
        fun(State@2) -> Is_found(erlang:element(2, State@2)) end,
        {0, Initial_state}
    ),
    gleam@result:map(
        _pipe@1,
        fun(List) ->
            gleam@list:map(List, fun(T) -> erlang:element(2, T) end)
        end
    ).

-file("src/search_algorithms.gleam", 46).
-spec dijkstra_generalized(
    fun(({integer(), GKS}) -> list({integer(), GKS})),
    fun((GKS) -> boolean()),
    GKS
) -> {ok, {integer(), list(GKS)}} | {error, nil}.
dijkstra_generalized(Get_next_estimate_state_pairs, Is_found, Initial_state) ->
    Unpack = fun(Estimate_state_pairs) -> case Estimate_state_pairs of
            [] ->
                {0, []};

            _ ->
                Last@1 = case gleam@list:last(Estimate_state_pairs) of
                    {ok, Last} -> Last;
                    _assert_fail ->
                        erlang:error(#{gleam_error => let_assert,
                                    message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                    file => <<?FILEPATH/utf8>>,
                                    module => <<"search_algorithms"/utf8>>,
                                    function => <<"dijkstra_generalized"/utf8>>,
                                    line => 59,
                                    value => _assert_fail,
                                    start => 2006,
                                    'end' => 2059,
                                    pattern_start => 2017,
                                    pattern_end => 2025})
                end,
                Fst = erlang:element(1, Last@1),
                Snd = gleam@list:map(
                    Estimate_state_pairs,
                    fun(T) -> erlang:element(2, T) end
                ),
                {Fst, Snd}
        end end,
    Result = internal@generalized_search:generalized_search(
        internal@search_container:new_lifo_heap(),
        fun(T@1) -> erlang:element(2, T@1) end,
        fun(Left, Right) ->
            erlang:element(1, Left) < erlang:element(1, Right)
        end,
        Get_next_estimate_state_pairs,
        fun(T@2) -> Is_found(erlang:element(2, T@2)) end,
        {0, Initial_state}
    ),
    gleam@result:map(Result, Unpack).

-file("src/search_algorithms.gleam", 81).
?DOC(" Dijkstra w/ associated transition costs\n").
-spec dijkstra_assoc(
    fun((GKZ) -> list({GKZ, integer()})),
    fun((GKZ) -> boolean()),
    GKZ
) -> {ok, {integer(), list(GKZ)}} | {error, nil}.
dijkstra_assoc(Get_next_states, Is_found, Initial_state) ->
    Get_next_estimate_state_pairs = fun(Estimate_state_pair) ->
        {Current_cost, Current_state} = Estimate_state_pair,
        Next_states = Get_next_states(Current_state),
        _pipe = Next_states,
        gleam@list:map(
            _pipe,
            fun(State_cost_tuple) ->
                {Current_cost + erlang:element(2, State_cost_tuple),
                    erlang:element(1, State_cost_tuple)}
            end
        )
    end,
    dijkstra_generalized(Get_next_estimate_state_pairs, Is_found, Initial_state).

-file("src/search_algorithms.gleam", 101).
?DOC(" Dijkstra\n").
-spec dijkstra(
    fun((GLC) -> list(GLC)),
    fun((GLC, GLC) -> integer()),
    fun((GLC) -> boolean()),
    GLC
) -> {ok, {integer(), list(GLC)}} | {error, nil}.
dijkstra(Get_next_states, Get_next_cost, Is_found, Initial_state) ->
    Get_next_estimate_state_pairs = fun(Estimate_state_pair) ->
        {Current_cost, Current_state} = Estimate_state_pair,
        Next_states = Get_next_states(Current_state),
        Next_costs = gleam@list:map(
            Next_states,
            fun(Next_state) ->
                Get_next_cost(Current_state, Next_state) + Current_cost
            end
        ),
        gleam@list:zip(Next_costs, Next_states)
    end,
    dijkstra_generalized(Get_next_estimate_state_pairs, Is_found, Initial_state).

-file("src/search_algorithms.gleam", 122).
-spec a_star_generalized(
    fun(({integer(), {GLF, integer()}}) -> list({integer(), {GLF, integer()}})),
    fun((GLF) -> integer()),
    fun((GLF) -> boolean()),
    GLF
) -> {ok, {integer(), list(GLF)}} | {error, nil}.
a_star_generalized(
    Get_next_estimate_state_pairs,
    Approx_remaining_cost,
    Is_found,
    Initial_state
) ->
    Unpack = fun(Estimate_state_pairs) -> case Estimate_state_pairs of
            [] ->
                {0, []};

            _ ->
                Last@1 = case gleam@list:last(Estimate_state_pairs) of
                    {ok, Last} -> Last;
                    _assert_fail ->
                        erlang:error(#{gleam_error => let_assert,
                                    message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                    file => <<?FILEPATH/utf8>>,
                                    module => <<"search_algorithms"/utf8>>,
                                    function => <<"a_star_generalized"/utf8>>,
                                    line => 136,
                                    value => _assert_fail,
                                    start => 4562,
                                    'end' => 4615,
                                    pattern_start => 4573,
                                    pattern_end => 4581})
                end,
                Fst = erlang:element(2, erlang:element(2, Last@1)),
                Snd = gleam@list:map(
                    Estimate_state_pairs,
                    fun(States) ->
                        erlang:element(1, erlang:element(2, States))
                    end
                ),
                {Fst, Snd}
        end end,
    Result = internal@generalized_search:generalized_search(
        internal@search_container:new_lifo_heap(),
        fun(Estimate_state_pair) ->
            erlang:element(1, erlang:element(2, Estimate_state_pair))
        end,
        fun(Left, Right) ->
            erlang:element(1, Left) < erlang:element(1, Right)
        end,
        Get_next_estimate_state_pairs,
        fun(Estimate_state_pair@1) ->
            Is_found(
                erlang:element(1, erlang:element(2, Estimate_state_pair@1))
            )
        end,
        {Approx_remaining_cost(Initial_state), {Initial_state, 0}}
    ),
    gleam@result:map(Result, Unpack).

-file("src/search_algorithms.gleam", 165).
?DOC(" A* w/ associated transition costs\n").
-spec a_star_assoc(
    fun((GLM) -> list({GLM, integer()})),
    fun((GLM) -> integer()),
    fun((GLM) -> boolean()),
    GLM
) -> {ok, {integer(), list(GLM)}} | {error, nil}.
a_star_assoc(Get_next_states, Approx_remaining_cost, Is_found, Initial_state) ->
    Get_next_estimate_state_pairs = fun(Estimate_state_pair) ->
        {_, {Current_state, Current_cost}} = Estimate_state_pair,
        _pipe = Get_next_states(Current_state),
        gleam@list:map(
            _pipe,
            fun(State_cost_tuple) ->
                Remaining = Approx_remaining_cost(
                    erlang:element(1, State_cost_tuple)
                ),
                Next_cost = Current_cost + erlang:element(2, State_cost_tuple),
                Next_estimate = Next_cost + Remaining,
                {Next_estimate,
                    {erlang:element(1, State_cost_tuple), Next_cost}}
            end
        )
    end,
    a_star_generalized(
        Get_next_estimate_state_pairs,
        Approx_remaining_cost,
        Is_found,
        Initial_state
    ).

-file("src/search_algorithms.gleam", 193).
?DOC(" A*\n").
-spec a_star(
    fun((GLP) -> list(GLP)),
    fun((GLP, GLP) -> integer()),
    fun((GLP) -> integer()),
    fun((GLP) -> boolean()),
    GLP
) -> {ok, {integer(), list(GLP)}} | {error, nil}.
a_star(
    Get_next_states,
    Get_next_cost,
    Approx_remaining_cost,
    Is_found,
    Initial_state
) ->
    Get_next_estimate_state_pairs = fun(Estimate_state_pair) ->
        {_, {Current_state, Current_cost}} = Estimate_state_pair,
        Next_states = Get_next_states(Current_state),
        gleam@list:map(
            Next_states,
            fun(Next_state) ->
                Remaining = Approx_remaining_cost(Next_state),
                Next_cost = Current_cost + Get_next_cost(
                    Current_state,
                    Next_state
                ),
                Next_estimate = Next_cost + Remaining,
                {Next_estimate, {Next_state, Next_cost}}
            end
        )
    end,
    a_star_generalized(
        Get_next_estimate_state_pairs,
        Approx_remaining_cost,
        Is_found,
        Initial_state
    ).
Operator	Description	Example
name:	Match package name. Supports * wildcards and repo/package form	name:phx* or name:hexpm/phoenix
description:	Full-text search of package descriptions	description:auth
depends:	Packages depending on a given package. Supports repo:package form	depends:ecto or depends:hexpm:ecto
build_tool:	Filter by build tool	build_tool:mix
updated_after:	Packages updated after an ISO8601 datetime	updated_after:2025-01-01T00:00:00Z
extra:	Match custom metadata (key,value). Nested keys are separated by commas	extra:license,MIT