locked
Can I C++ Const an Immutable F# Array Function Parameter? RRS feed

  • Question

  • The fact that everything in F# is immutable by default is a great benefit to me in that it keeps me from doing many retarded things that would cause bugs.  This feature alone makes F# worlds better than VB.NET and C#, but I am still new to the language and have some things to learn.  I know that the F# List is immutable and can’t be changed when it is passed into a function.   For this reason, I prefer F# Lists over their mutable counterpart F# Arrays; unfortunately, immutable F# Lists have an O(N) lookup time compared to the O(1) lookup time of F# Arrays.  This presents a bit of a problem for me.


    As I understand F# now, if I want the O(1) lookup time of F# Arrays,  I must apparently sacrifice the benefit of immutability and expose myself to potential bugs as I create more opportunities for my stupidity to abound.  In C++, I can pass a mutable array to a function and keep that function from modifying the mutable array by applying the “const” keyword to the array param of the function.  Here is some demo code of how I might do that:


    #include "stdafx.h"
    #include <iostream>

    using namespace std;

    // Gets the average of the "numList"
    //
    // The "int const * const" type on
    // "numList" ensures that numList can't be changed inside this
    // "average" function even if the passed in array is mutable
    //
    // If I were to try to assign anything to numList inside this function,
    // I would get a comile time error
    int const average(int const * const numList, int const length) {
    unsigned int testSum = 0;
    for (unsigned int i = 0; i < length; i++) {
    testSum += numList[i];
    }
    return testSum / length;
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
    // A mutable C++ array of test scores
    int const testScoresLength = 4;
    int testScores[testScoresLength] = { 70, 90, 85, 100};
    cout << average(testScores, testScoresLength) << endl;
    return 0;
    }



    On the other hand, in F# I’m not aware of any such “const” keyword, so to perform an "averageArray" function like the one mentioned in the previous C++ example, I could possibly be stupid and write something like the following:

     

     
      
    (* This broken array averaging code is based of of the logically 
       correct MSDN Example found here:   
       http://msdn.microsoft.com/en-us/library/ee340228.aspx  
       To demonstrate my need to make input parameters immutable, I have
       inserted bugs into the code *)
    let averageArray (array : int[]) = 
       array.[0] <- 0   (* BUG: Programer went nuts and changed input *)
       array.[1] <- 0   (* BUG: Programer went nuts and changed input *)
       array.[2] <- 0   (* BUG: Programer went nuts and changed input *)
       array.[3] <- 0   (* BUG: Programer went nuts and changed input *)
       (* This logical and working code from MSDN is affected by the 
          programmer stupidity demonstrated above *)
       (Array.fold 
       (fun acc elem -> acc + elem) 0 array / array.Length)   
     
     
    (* A mutable F# array of test scores *)
    let testScores = [| 70; 90; 85; 100 |]
    printfn "%A" testScores
     
     
    (* The "averageArray" function has issues, not only does it return 
       the wrong answer, but it changes the mutable array testScores.
       Even though testScores is mutable, there should be some sort of
       keyword or construct that I can apply to "averageArray" to keep 
       it from jacking with its inputs.  Can you tell me what contruct
       or keyword I need to use? *)
    let avg = averageArray testScores
    printf "Average is: %d\n" avg
    printfn "%A" testScores



    Can any of you tell me some way I can alter the above F# code so that the “averageArray” function will cause the compiler to scream at my face when I try to alter the mutable “array” parameter? 
     
    In the F# example, I want “testScores” to remain mutable but I want the averageArray function to be contractually obligated to not change it inputs in anyway.    If this can’t be done with native F#, can you tell me:
    1. How I might request such a const-correct feature in the next version of F#?
    2. How I might use the Microsoft Code Contract engine to keep the averageArray function from changing the “array” parameter?

    With Appreciation,

    Shawn
    F# is Awesome






    • Edited by Shawn Eary Sunday, July 10, 2011 4:46 AM bad formatting
    Sunday, July 10, 2011 4:18 AM

Answers

All replies

  • Instead of passing the data (an array), you can pass an interface, composed of a function that given an int denoting the index returns an int, and a range. You then implement the average using the Seq module instead of Array.

    Actually, for this kind of operations that work on the entire array, you can use seq<int> instead of int[] without being affected by the O(n) cost of random access, as random access is not needed.

    I found that in my experience, mappings fit many of the cases where random access is needed. Instead of passing the datastructure itself (Dictionary, Map, Array), I pass an accessing function and use that instead. It leaves the door open for switching between different map types.

     


    Sunday, July 10, 2011 10:22 AM
  • Instead of passing the data (an array), you can pass an interface, composed of a function that given an int denoting the index returns an int, and a range...

    That sounds interesting and it might work for me.  Are you suggesting I try something like this?

     

    (* A mutable F# array of numbersToAdd *)
    let numsToAdd = [| 8; 1; 2; 3; 4 |]

    (* My guess of a function to return an element of an array as 
       Mr. Deneux suggested *)
    let arrayElementGetter (array : int[]) x = (array.[x], array.Length)

    (* My guess at the way to make an O(1) ReadOnly accessor function 
       to "numsToAdd" as Mr. Deneux suggested *) 
    let numsToAddGetter = arrayElementGetter numsToAdd

    (* My attempt to make a function that takes an arrayElementGetter
       curried to a specific integer array and then sums the values of
       that array as Mr. Deneux suggested.  By using the mapping that 
       Mr. Deneux suggested, I can ensure that the original array 
       is not manipulated in any way but still get O(1) random access.
       
       Note: In this hypotetical example, random access isn't actually 
             necessary since we are just summing elements, however, this 
             example "might" demonstrate how I could use Mr. Denuex's 
             approach to keep the original array from being modified. *)
    let addArray (aMap : int -> (int * int))  =  
       (* BEGIN: I'm glad the compiler doesn't allow this  
          If I understand Mr. Deneux's suggestion correctly it seems to 
          work since F# gives me an invalid expression on the left side
          of the argument error on the below statement.  So this implies
          that this addArray function has no way of changing the orignal 
          mutable array *) 
       (* fst(aMap 3) <- 8  *) 
       (* END  : I'm glad the compiler doesn't allow this *) 
       let rec m_sumArray (aMap : int -> (int * int)) (start : int) =
          let arrayLen = snd (aMap 0)     (* Index does not matter here
                                             just getting length *)       
          if start < arrayLen then
             let arrayVal = fst (aMap start)
             arrayVal + (m_sumArray aMap (start+1))
          else
             0 
       m_sumArray aMap 0
        
    let theSum = addArray numsToAddGetter

     

    Thanks,

    Shawn


    Monday, July 11, 2011 4:00 AM
  • I wouldn't have aMap return a pair, just the value by itself. The length should be an additional parameter. But that's just a minor style issue, you understood me right.
    Monday, July 11, 2011 8:05 AM
  • If you want an "immutable array", what you need is a type that implements System.Collections.Generic.IList<T> but doesn't allow any of the array's data to be changed. Here's something I just threw together...no warranties as to whether it works correctly or not though :)

    Note that using IList<T> this way means you'll only get errors at runtime. If you want the F# compiler to help pick up any errors, add some properties like .Length and .Item (with a 'getter' only) -- but note that you'll lose some flexibility here, as your code will be tied to this specific type (whereas if you write your code to work with IList<T> instances, you could pass in normal arrays, ResizeArrays and so forth).

    One last thought -- this is really only worth using if you need O(1) random access. If you're just summing the values of the array (for example), you might as well just use an F# list or seq (as Johann said earlier).

    /// Wraps an array to provide immutability and O(1) random access.
    type ImmutableArray<'a> (arr : 'a[]) =
     interface System.Collections.IEnumerable with
     //
     member this.GetEnumerator () = arr.GetEnumerator ()
    
     interface System.Collections.Generic.IEnumerable<'a> with
     //
     member this.GetEnumerator () = (arr :> System.Collections.Generic.IEnumerable<'a>).GetEnumerator ()
    
     interface System.Collections.Generic.ICollection<'a> with
     //
     member this.Add _ = raise (System.NotSupportedException ("Cannot add elements to an ImmutableArray."))
     //
     member this.Clear () = raise (System.NotSupportedException ("Cannot clear an ImmutableArray."))
     //
     member this.Contains item = System.Array.IndexOf(arr, item) >= 0
     //
     member this.CopyTo (arr, idx) = System.Array.Copy (arr, 0, arr, idx, Array.length arr)
     //
     member this.Count with get () = Array.length arr
     //
     member this.IsReadOnly with get () = true
     //
     member this.Remove _ = raise (System.NotSupportedException ("Cannot remove elements from an ImmutableArray."))
    
     interface System.Collections.Generic.IList<'a> with 
     //
     member this.IndexOf item = System.Array.IndexOf (arr, item)
     //
     member this.Insert (_, _) = raise (System.NotSupportedException ("Cannot insert elements into an ImmutableArray.")) 
     //
     member this.Item
     with get idx = arr.[idx]
     and set idx item = raise (System.NotSupportedException ("Cannot set the value of an element within an ImmutableArray.")) 
     //
     member this.RemoveAt _ = raise (System.NotSupportedException ("Cannot remove elements from an ImmutableArray."))


     




    • Edited by Jack Pappas Monday, July 11, 2011 4:18 PM Added some extra details about the implementation.
    Monday, July 11, 2011 4:11 PM
  • Also, I don't see how you need O(1) lookup time when you are processing the whole sequence.

    That is the real question: What is your problem such that you do need a direct lookup to a specific element of the collection?

    In the example above you didn't and I'm thinking that most of the time, it's possible to model the problem in a different way such that you do not need direct lookup.

    Monday, July 11, 2011 5:03 PM
  • I believe for this type of data structure you should look at inheriting from ReadOnlyCollection<T> http://msdn.microsoft.com/en-us/library/ms132474.aspx rather than IList specifically.
    • Marked as answer by Shawn Eary Wednesday, July 13, 2011 4:34 AM
    Tuesday, July 12, 2011 9:47 PM
  • This should do the trick:

     

    let arr = [|1..5|]
    let readableArr = System.Array.AsReadOnly([|1..5|])
    readableArr.[0] <- 2
    

     Now you get a compile time error on the last line: Property 'Item' cannot be set.

    Tuesday, July 12, 2011 9:54 PM
  • I wouldn't have aMap return a pair, just the value by itself. The length should be an additional parameter. But that's just a minor style issue, you understood me right.

    Ok thanks.
    Wednesday, July 13, 2011 3:29 AM
  • Also, I don't see how you need O(1) lookup time when you are processing the whole sequence.
    You're right I don't. It was a hypothetical example to see if there was a way to apply some C++ "const" like keyword to a function parameter so mutable datatypes that are passed in can't be changed. This is the main reason I like C++ so much. C++ gives me the ability to lock down every facet of every parameter/returnValue involved. VB.NET and C# don't give me that ability. That's one major source of irritation for me with VB.NET and C#. Because of things like this, VB.NET and C# are highly susceptible to side effects. On the other hand, F# is largely immune to side effect unless you are using arrays in the manner mentioned above. But this thread has already given me a few ways to combat the problem. So in my opinion, F# is loads better than C# and VB.NET.
    What is your problem such that you do need a direct lookup to a specific element of the collection? In the example above you didn't and I'm thinking that most of the time, it's possible to model the problem in a different way such that you do not need direct lookup.
    You're right, I don't need O(1) access in the above example. The example was contrived to try and explain that I wanted to apply a C++ "const" style keyword to F# parameters so the F# function couldn't perform a side effect on the parameters even if they were mutable.

    The actual problem that triggered my thought was being able to "randomly" select numerous strings from a collection. I think that randomly selecting values from a ReadOnly array of strings is fast; on the other hand, I think that randomly selecting values from a very large readonly list of strings takes a long time. That's why I'm trying to go with an array.
    Wednesday, July 13, 2011 3:48 AM
  • I think that randomly selecting values from a ReadOnly array of strings is fast; on the other hand, I think that randomly selecting values from a very large readonly list of strings takes a long time.

    Why do you think that? The only overhead with `ReadOnlyCollection<>` is the indirection cost of accessing an array through an `IList<>` interface. Is that actually a bottleneck for you?

    Wednesday, July 13, 2011 4:02 AM
  • Mr. Quirk:

    I feel that your answer is the best and that it is very close to what I am looking for.   Looking at the documentation for ReadOnlyCollection<T>, it "seems" as if the collection has O(1) lookup but yet preserves immutability.  At this point, it seems as if your ReadOnlyCollection solution does everything I need:

     

    (* I like Mr. Quirk's suggestion.  In fact, I think it is so close 
       to what I need, it might just solve some VB.NET and C# side effect
       issues I have been having; however, we all know that F# is 
       waaaaaaaay better than VB.NET and C# :o)  *)
    let addArray (aToAdd : (System.Collections.ObjectModel.ReadOnlyCollection<int>))  =  
       (* Thanks to Mr. Quirk's post, the following statement now issues
          an error because C++ const-correctness seems to be simulated *)
       (* aToAdd.[0] <- 0 *)(* NET won't let programmer be stupid here *)
       let mutable sum = 0 
       for i = 0 to (aToAdd.Count - 1) do 
          sum <- sum + aToAdd.[i]
       sum

    (* A mutable F# array of numbersToAdd *)
    let numsToAdd = [| 8; 1; 2; 3; 4 |]

    (* Thank's again to Mr. Quirk's suggestion.  The compiler forces the 
       user to pass in System.Collections.ObjectModel.ReadOnlyCollection<int>
       and thereby does not allow the mutable array numsToAdd to be passed
       in *) 
    (* let theSum = addArray numsToAdd *) (* Compiler won't allow this :o) *)

    (* Thanks to Mr. Quirk, the Compiler *forces* the user to cast the input
       as a ReadOnly Array thereby guaranteeing that the function AddArray
       can't change "numsToAdd"  This is absolutely awesome!!! *) 
    let theSum = addArray (System.Array.AsReadOnly(numsToAdd))

     

    With Appreciation,

    Shawn

     


    Wednesday, July 13, 2011 4:34 AM
  • I think that randomly selecting values from a ReadOnly array of strings is fast; on the other hand, I think that randomly selecting values from a very large readonly list of strings takes a long time.

    Why do you think that? The only overhead with `ReadOnlyCollection<>` is the indirection cost of accessing an array through an `IList<>` interface. Is that actually a bottleneck for you?

    "I think that randomly selecting values from a very large readonly list of strings takes a long time." - Sorry, I was referring to a traditionally implemented linked list.  I wasn't necessarily referring to IList which appears to be implemented as an array.   So no, the use of ReadOnlyCollection as Mr. Quirk suggested is not likely a bottleneck for me. 

    I think this post is getting waaaay of topic.  The original idea was to see if there was some way the compiler could guarantee that all parameters passed into an F# Function could never be changed regardless of mutability.  In C++ "const" is used ensure this with a high degree of reliability, but in languages like VB.NET and C#, I have had a difficult time ensuring const correctness without making deep copies of data.

    Now that I have read Mr. Quirks post, I know that in VB.NET and C#, I do have a way of ensuring that functions can't change arrays that are passed in.  I just have to make sure all array parameters to VB.NET and C# methods pass parameters of type ReadOnlyCollection.  I was so used to doing this with "const" in C++ that I didn't think of a way to do it in *.NET. 

    With all of that being said, I will still prefer F# for its by default immutability and F# Lists instead of F# Arrays. 

    Wednesday, July 13, 2011 4:59 AM
  • If you want an "immutable array", what you need is a type that implements System.Collections.Generic.IList<T> but doesn't allow any of the array's data to be changed. Here's something I just threw together...no warranties as to whether it works correctly or not though :)

    Mr. Pappas (+1):

    Your suggestion is useful, but I prefer Mr. Quirk's solution.

    With Thanks,

    Shawn

    Wednesday, July 13, 2011 5:02 AM