Serge D. Mechveliani wrote:
>
> People,
> can you, please, answer the following beginner questions about the Spad
> language and library?
>
> Membership to a fixed finite set
> --------------------------------
> I put
> delimiters() : Set Character ==
> construct( map(char, ["(", ")", ..., ",", ":", ...]) )
> :: Set Character
> -- a set of about 30 characters
>
> delimiter? x == member?(x, delimiters())
>
> Is this a reasonable way to define this predicate?
Almost.
> Is it computed fast -- by the binary search?
No, 'member?' uses linear search. OTOH a few years ago one
guy investigated when binary search is faster compared to
linear search and in C he came out with treshold of 16,
that is below length 16 linear search was faster.
BTW, as long as character set is small the fast way is via
table lookup: use character code as index to table containing
true for members of the set and false otherwise. Unicode
(which may be in use) is not a small character set, but
special characters normally come from ASCII subset, so
codes are smaller than 128. So something like:
delims := new(128, false)$PrimitiveArray(Boolean)
for c in ["(", ")", ..., ",", ":", ...] repeat
delims(ord(char(c))) := true
delimiter?(x : Character) ==
n := ord(x)
n < 128 and delims(n)
> When delimiter? is applied repeatedly in different places in a
> program, does this lead to repeated build of the set delimiters() ?
In your version yes.
> May be, put
> delims := delimiters()
>
> and then, use delims in the scope?
>
Yes.
>
> Generalization of String and List
> ---------------------------------
> I define
> dropWhileInStr(p: Character -> Bool, xs: String) : String ==
> empty? xs => ""
> p first(xs) => dropWhileInStr(p, delete(xs, 1))
> xs
>
> for dropping first letters from xs which satisfy a predicate p.
> It this a reasonable code?
IMHO reasonable, but potentally quite inefficient: delete creates
copy. If the string has length n delete allocates new string
of length n - 1 and then copies characters. Potentially you
may have n characters which satisfy predicate p, so the method
is O(n^2) (and constants are not so small because you trigger
memory allocation).
> I would like to generalize it for working uniformly for String and
> List T, something like
>
> package Foo(T : Type, Agg : Aggregate T ??)
> ...
> add
> dropWhile(p: T -> Bool, xs : Agg) : Agg ==
> empty? xs => xs
> ...
> What might be the code?
>
package Foo(T : Type, Agg : FiniteLinearAggregate(T)
...
dropWhile(p: T -> Bool, xs : Agg) : Agg ==
i := minIndex(xs)
j := position((el : T) : Boolean +-> not(p(el)), xs)
delete(xs, i..j)
>
> Function composition
> --------------------
> I write map(x +-> not p(x), xs) for xs :: List T.
> But it is nicer to write
> map((not . p), xs),
> where `.' is composition of functions
> (in Haskell, it is simpler: map (not . p) xs ).
>
> What the Spad library has to replace this `.' ?
>
You can define your own package like:
FunctionComposition(S : Type, T : Type, U : Type) with
"*" : ((S -> T), (T, U)) -> (S, U)
== add
f * g == x +-> f(g(x))
but before you use such an '*' you need first to do
import FunctionComposition(S, T, U)
(with S, T, U) replaced by appropriate types. IMHO this need
for import defeats the purpose. Of course '*' is an example,
you may use different operator. You may even try to define
new meaning for '.', but since dot normally means function
application, that is f . g is the same as f(g) this can lead
to confusion and bugs.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
