列表被视为长度函数的整数

Question

我正在尝试使用 Karate Chop Kata 来学习 Erlang。 我将 kata 中提供的 runit 测试翻译为 eunit 测试，并编写了一个小函数来执行手头的任务。

-module(chop).
-export([chop/2]).
-import(lists).
-include_lib("eunit/include/eunit.hrl").
-ifdef(TEST).
chop_test_() -> [
    ?_assertMatch(-1, chop(3, [])),
    ?_assertMatch(-1, chop(3, [1])),
    ?_assertMatch(0,  chop(1, [1])),
 ....several asserts deleted for brevity...
].
-endif.

chop(N,L) -> chop(N,L,0);
chop(_,[]) -> -1.
chop(_, [],_) -> -1;
chop(N, L, M) ->
    MidIndex = length(L) div 2,
    MidPoint = lists:nth(MidIndex,L),
    {Left,Right} = lists:split(MidIndex,L),
    case MidPoint of 
    _ when MidPoint < N -> chop(N,Right,M+MidIndex);
    _ when MidPoint =:= N -> M+MidIndex;
    _ when MidPoint > N -> chop(N,Left,M)
    end.

编译正常。但是运行测试会（除其他外）出现以下失败：

::error:badarg
 in function erlang:length/1
  called as length(1)
 in call from chop:chop/3

我尝试了声明 Chop(N,[L],M) .... 和使用 length([L]) 的不同排列，但还没有能够解决这个问题。 欢迎任何建议。

附： 正如你可能已经猜到的，我对 Erlang 很狂热。

Answer 1

所以我现在时间紧迫，但我看到的第一个问题是这

chop(N,L) -> chop(N,L,0);
chop(_,[]) -> -1.

是错误的，因为 Chop(N,L) 总是匹配。 颠倒这些条款，看看会带来什么结果。

除此之外，在 1 元素列表的情况下，nth(0, [1]) 将失败。 我觉得这些列表可能是 1 索引的。

Answer 2

作为最重要的学习内容，您应该意识到，在 erlang 中使用二分搜索列表是错误的想法，因为 lists:nth/2 不是 O(1) 而是 O(N) 操作。 尝试 list_to_tuple/1 并在元组上执行此操作。 这是更值得的工作。

在 array 模块上尝试也是值得的。

Answer 3

函数 erlang:length/1 返回列表的长度。

您调用了 length(1) 并且 1 不是列表。

length([1]) 将返回 1
length([1,2,3,4[) 将返回 4
等等，等等...

Answer 4

看来，结合本·休斯的言论就可以解决这个问题。 为了完整起见，我在下面粘贴了我的二分搜索的通过测试的实现。

chop(_,[]) -> -1;
chop(N,L) -> 
    Array = array:from_list(L),
chop(N,Array, 0, array:size(Array)-1).
chop(N, L, K, K) -> 
    Element = array:get(K,L),
    if 
        Element == N -> K; 
        true -> -1
    end;
chop(_, _, K, M) when M < K -> -1;
chop(N, L, K, M) ->
    MidIndex = K + ((M - K) div  2),
    MidPoint = array:get(MidIndex,L),
    case MidPoint of 
        N -> MidIndex;
        _ when MidPoint < N -> chop(N,L,MidIndex+1,M);
        _ -> chop(N,L,K,MidIndex-1)
    end.