[erlang-questions] Avoiding case nesting

mayamatakeshi <>
Tue Sep 29 05:37:04 CEST 2009


On Tue, Sep 29, 2009 at 11:25 AM, Richard O'Keefe <> wrote:

> Let's generalise slightly:
>
> We are given a sequence of strings [S1,...,Sn].
> From this we want to generate a function F
> such that F(S) = {i,R} if i is the smallest integer
> for which S == Si ++ R, or F(S) = no_match otherwise.
>
> If we knew these strings at program construction time,
> we could just write
>
>        f(S1 ++ R) -> {1,R};
>        ...
>        f(Sn ++ R) -> {n,R};
>        f(_) -> no_match.
>
> This suggests one way to proceed: just write this text
> out to a file (with a suitable module header), compile
> it, load it, and use it.  Thanks to hot loading, you can
> repeat the process whenever you want to change the sequence
> of strings.
>

Yes, I realized that after reading Hynek's reply.


>
> At the other extreme,
>
> seek(Target, [Prefix|Prefixes], I) ->
>    case lists:prefix(Prefix, Target)
>      of true -> {I, lists:nthtail(length(Prefix), Target)}
>       ; false-> seek(Target, Prefixes, I+1)
>    end;
> seek(_, [], _) ->
>    no_match.
>
> searcher(Prefixes) ->
>    fun (Target) -> seek(Target, Prefixes, 1) end.
>
>
> The first trades high preprocessing time for low run time;
> the second trades high run time for low preprocessing time.
>
> Somewhere in the middle you could construct a ternary search
> tree.  In a language without run-time code generation, a
> ternary search tree would probably be the best way to go.
>

I will probably use on the fly compilation for a fixed set of prefixes. But
I will also need to test against dynamic sets of prefixes fetched from a DB.
So I will end up using the other end too.
Thanks for pointing the ternary search tree. I read about It and it is a
little over my head right now but I think I will eventually go with it if an
approach like searcher/seek doesn't show acceptable performance.


More information about the erlang-questions mailing list