headers
not norwegian swede | 2 Jul 10:32

conses in erlang?

can i use conses in erlang?
like in scheme, then i only need one function. is the range func in erlang ood erlang-style or is there a better way to do it?

(define (seq a b)
    (if (< a b)
        (cons a (seq (+ a 1) b))
        '()))

-module(test).
-export([range/2]).
     
range(Start, End) when Start < End, is_integer(Start), is_integer(End) ->
    seq(Start, End, []).

seq(Start, End, List) ->
    if Start =< End ->
        seq(Start + 1, End, List ++ [Start]);
    true ->
    List
end.

Ta semester! - sök efter resor hos Kelkoo.
Jämför pris på flygbiljetter och hotellrum: http://www.kelkoo.se/c-169901-resor-biljetter.html 
<div>
<table cellspacing="0" cellpadding="0" border="0"><tr><td valign="top">can i use conses in erlang?<br>like in scheme, then i only need one function. is the range func in erlang ood erlang-style or is there a better way to do it?<br><br>(define (seq a b)<br>&nbsp;&nbsp;&nbsp; (if (&lt; a b)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (cons a (seq (+ a 1) b))<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; '()))<br><br>-module(test).<br>-export([range/2]).<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <br>range(Start, End) when Start &lt; End, is_integer(Start), is_integer(End) -&gt; <br>&nbsp;&nbsp;&nbsp; seq(Start, End, []).<br><br>seq(Start, End, List) -&gt;<br>&nbsp;&nbsp;&nbsp; if Start =&lt; End -&gt;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; seq(Start + 1, End, List ++ [Start]);<br>&nbsp;&nbsp;&nbsp; true -&gt;<br>&nbsp;&nbsp;&nbsp; List<br>end.<br>
</td></tr></table>
<br><table><tr><td>Ta semester! - s&ouml;k efter resor hos Kelkoo. <br>J&auml;mf&ouml;r pris p&aring; flygbiljetter och hotellrum: <a href="http://www.kelkoo.se/c-169901-resor-biljetter.html?partnerId=96914051">http://www.kelkoo.se/c-169901-resor-biljetter.html</a>
</td></tr></table>
</div>
Permalink | Reply |
headers
Christian S | 2 Jul 10:54

Re: conses in erlang?

You have the operator [End|Acc] to cons End on to the list Acc. See below.

Preferably, you implement seq from the end to the start.

seq(Start, End) -> seq(Start, End, []).

seq(Start, End, Acc) when Start =< End ->
   seq(Start, End-1, [End|Acc]);
seq(_, _, Acc) ->
   Acc.
Permalink | Reply |
headers
Lev Walkin | 2 Jul 11:03

Re: conses in erlang?

not norwegian swede wrote:
>   can i use conses in erlang?
> like in scheme, then i only need one function. is the range func in 
> erlang ood erlang-style or is there a better way to do it?
> 
> (define (seq a b)
>     (if (< a b)
>         (cons a (seq (+ a 1) b))
>         '()))
> 
> -module(test).
> -export([range/2]).
>      
> range(Start, End) when Start < End, is_integer(Start), is_integer(End) ->
>     seq(Start, End, []).
> 
> seq(Start, End, List) ->
>     if Start =< End ->
>         seq(Start + 1, End, List ++ [Start]);
>     true ->
>     List
> end.

seq(Start, End) when is_integer(Start), is_intger(End) ->
	seq(End, Start, []).

seq(End, Start, Acc) when Start >= End ->
	seq(End - 1, Start, [End|Acc]);
seq(_End, _Start, Acc) -> Acc.

this approach also has a linear complexity, instead of being O(N^2)
in your cas.

--

-- 
vlm
Permalink | Reply |
headers
Edwin Fine | 2 Jul 16:25

Re: conses in erlang?

Not knowing how new (or not) to Erlang the OP might be, I just wanted to make sure that the OP is aware of the existence of lists:seq/2, even if it's stating the obvious.

On Wed, Jul 2, 2008 at 5:03 AM, Lev Walkin <vlm <at> lionet.info> wrote:
not norwegian swede wrote:
>   can i use conses in erlang?
> like in scheme, then i only need one function. is the range func in
> erlang ood erlang-style or is there a better way to do it?
>
> (define (seq a b)
>     (if (< a b)
>         (cons a (seq (+ a 1) b))
>         '()))
>
> -module(test).
> -export([range/2]).
>
> range(Start, End) when Start < End, is_integer(Start), is_integer(End) ->
>     seq(Start, End, []).
>
> seq(Start, End, List) ->
>     if Start =< End ->
>         seq(Start + 1, End, List ++ [Start]);
>     true ->
>     List
> end.


seq(Start, End) when is_integer(Start), is_intger(End) ->
       seq(End, Start, []).

seq(End, Start, Acc) when Start >= End ->
       seq(End - 1, Start, [End|Acc]);
seq(_End, _Start, Acc) -> Acc.


this approach also has a linear complexity, instead of being O(N^2)
in your cas.

--
vlm
_______________________________________________
erlang-questions mailing list
erlang-questions <at> erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions




--
The great enemy of the truth is very often not the lie -- deliberate, contrived and dishonest, but the myth, persistent, persuasive, and unrealistic. Belief in myths allows the comfort of opinion without the discomfort of thought.
John F. Kennedy 35th president of US 1961-1963 (1917 - 1963) 
<div>
<p>Not knowing how new (or not) to Erlang the OP might be, I just wanted to make sure that the OP is aware of the existence of lists:seq/2, even if it's stating the obvious.<br><br></p>
<div class="gmail_quote">On Wed, Jul 2, 2008 at 5:03 AM, Lev Walkin &lt;<a href="mailto:vlm <at> lionet.info">vlm <at> lionet.info</a>&gt; wrote:<br><blockquote class="gmail_quote">
<div class="Ih2E3d">not norwegian swede wrote:<br>
&gt; &nbsp; can i use conses in erlang?<br>
&gt; like in scheme, then i only need one function. is the range func in<br>
&gt; erlang ood erlang-style or is there a better way to do it?<br>
&gt;<br>
&gt; (define (seq a b)<br>
&gt; &nbsp; &nbsp; (if (&lt; a b)<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; (cons a (seq (+ a 1) b))<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; '()))<br>
&gt;<br>
&gt; -module(test).<br>
&gt; -export([range/2]).<br>
&gt;<br>
&gt; range(Start, End) when Start &lt; End, is_integer(Start), is_integer(End) -&gt;<br>
&gt; &nbsp; &nbsp; seq(Start, End, []).<br>
&gt;<br>
&gt; seq(Start, End, List) -&gt;<br>
&gt; &nbsp; &nbsp; if Start =&lt; End -&gt;<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; seq(Start + 1, End, List ++ [Start]);<br>
&gt; &nbsp; &nbsp; true -&gt;<br>
&gt; &nbsp; &nbsp; List<br>
&gt; end.<br><br><br>
</div>seq(Start, End) when is_integer(Start), is_intger(End) -&gt;<br>
 &nbsp; &nbsp; &nbsp; &nbsp;seq(End, Start, []).<br><br>
seq(End, Start, Acc) when Start &gt;= End -&gt;<br>
 &nbsp; &nbsp; &nbsp; &nbsp;seq(End - 1, Start, [End|Acc]);<br>
seq(_End, _Start, Acc) -&gt; Acc.<br><br><br>
this approach also has a linear complexity, instead of being O(N^2)<br>
in your cas.<br><br>
--<br>
vlm<br><div>
<div></div>
<div class="Wj3C7c">_______________________________________________<br>
erlang-questions mailing list<br><a href="mailto:erlang-questions <at> erlang.org">erlang-questions <at> erlang.org</a><br><a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br><br>
</div>
</div>
</blockquote>
</div>
<br><br clear="all"><br>-- <br>The great enemy of the truth is very often not the lie -- deliberate, contrived and dishonest, but the myth, persistent, persuasive, and unrealistic. Belief in myths allows the comfort of opinion without the discomfort of thought.<br>
John F. Kennedy 35th president of US 1961-1963 (1917 - 1963)
</div>
Permalink | Reply |
headers
Richard A. O'Keefe | 3 Jul 02:41

Re: conses in erlang?


On 2 Jul 2008, at 8:33 pm, not norwegian swede wrote:
> can i use conses in erlang?

[ H | T ] in Erlang is precisely the same thing as (cons H T) in Scheme.
>
> like in scheme, then i only need one function.
> is the range func in erlang ood erlang-style or is there a better  
> way to do it?

I'm having trouble understanding "range func" and "ood erlang-style".
Is that OOD (Object-Oriented Development) or (g)ood?
>
> (define (seq a b)
>     (if (< a b)
>         (cons a (seq (+ a 1) b))
>         '()))

It is good Scheme style to provide comments.
The missing comment here seems to be

	;; (seq start end) => (start start+1 ... end-1)
	;; that is, the integer interval [start,end).

That's a good definition in Scheme because Scheme uses 0 origin
indexing and uses a [start,end) convention for slices.

In Scheme I might have written

	(define (seq Start End)
	  (do ((I (- End 1) (- I 1))
                (R '()       (cons I R)))
               ((< I Start) R)))

Testing the two versions gave me a real shock:  the "do" version
worked just fine, but the body-recursive version actually crashed
the SCM 5b3 system I was testing in.
>
>
> -module(test).
> -export([range/2]).
>
> range(Start, End) when Start < End, is_integer(Start),  
> is_integer(End) ->
>     seq(Start, End, []).
>
> seq(Start, End, List) ->
>     if Start =< End ->
>         seq(Start + 1, End, List ++ [Start]);
>     true ->
>     List
> end.

The seq/3 function here uses an 'if'; I believe that Erlang style
prefers clause guards to ifs.  So

range(Start, End) when is_integer(Start), is_integer(End) ->
     seq(Start, End, []).

seq(Start, End, List) when Start <= End ->
     seq(Start + 1, End, List ++ [Start]);
seq(_, _, List) ->
     List.

There is an important difference between your Scheme code and
your Erlang code:  they do not compute the same result.  Your
range(1, 4) => [1,2,3,4] whereas
(seq 1 4) => (1 2 3).
Since Erlang uses 1 origin and (sadly) prefers to use
intervals [L,U] rather than [L,U), this is probably what you
meant, but it is definitely important enough to include a
comment to that effect.

The next thing is that Erlang lists are *EXACTLY* like Scheme
lists.  (More precisely, like R6RS lists, which are by
default immutable.)  And L1 ++ L2 is how Erlang expresses
(append L1 L2).  When you are taught Scheme, you are taught
to add new elements at the LEFT end of a list (because that
is O(1)) instead of the right end (because that is O(n)).
[X] ++ L is OK, because it's [X | L] (Scheme `(,X ,@L)).
L ++ [X] is very seldom a good thing to do.

A recursive version that agrees with your Scheme version,
except for including the upper bound in the result, is

range(Start, End) when is_integer(Start), is_integer(End) ->
     count_up(Start, End).

count_up(Start, End) when Start <= End ->
     [Start | count_up(Start+1, End)];
count_up(_, _) ->
     [].

A tail recursive version like my "do" version is

range(Start, End) when is_integer(Start), is_integer(End) ->
     count_down(Start, End, []).

count_down(Start, End, List) when Start <= End ->
     count_down(Start, End-1, [End|List]);
count_down(_, _, List) ->
     List.
Permalink | Reply |
headers
Johnny Billquist | 3 Jul 11:35

Re: conses in erlang?

Richard A. O'Keefe skrev:
> On 2 Jul 2008, at 8:33 pm, not norwegian swede wrote:
>> can i use conses in erlang?
> 
> [ H | T ] in Erlang is precisely the same thing as (cons H T) in Scheme.

But it's totally the same as a cons in Lisp.
But maybe they are similar enough for pm's needs to not require any further 
discussion?

	Johnny

--

-- 
Johnny Billquist                  || "I'm on a bus
                                   ||  on a psychedelic trip
email: bqt <at> softjar.se             ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol
Permalink | Reply |
headers
Johnny Billquist | 3 Jul 13:11

Re: conses in erlang?

Johnny Billquist wrote:
> Richard A. O'Keefe skrev:
>> On 2 Jul 2008, at 8:33 pm, not norwegian swede wrote:
>>> can i use conses in erlang?
>> [ H | T ] in Erlang is precisely the same thing as (cons H T) in Scheme.
> 
> But it's totally the same as a cons in Lisp.

Argh! I meant to say that it's *not* entirely the same thing as a cons 
in Lisp (my memory of Scheme is rusty, so I can't say for sure how a 
cons in Scheme works).

> But maybe they are similar enough for pm's needs to not require any further 
> discussion?

	Johnny
Permalink | Reply |
headers
Richard A. O'Keefe | 4 Jul 04:19

Re: conses in erlang?


On 3 Jul 2008, at 11:11 pm, Johnny Billquist wrote:

> Johnny Billquist wrote:
>> Richard A. O'Keefe skrev:
>>> On 2 Jul 2008, at 8:33 pm, not norwegian swede wrote:
>>>> can i use conses in erlang?
>>> [ H | T ] in Erlang is precisely the same thing as (cons H T) in  
>>> Scheme.
>> But it's totally the same as a cons in Lisp.
>
> Argh! I meant to say that it's *not* entirely the same thing as a  
> cons in Lisp (my memory of Scheme is rusty, so I can't say for sure  
> how a cons in Scheme works).

That's why I said it's precisely the same thing as cons in SCHEME.
In the R6RS specification of Scheme, set-car! and set-cdr! are no
longer part of the core language; they are in an optional module.
Permalink | Reply |

Gmane